剑指offer:85-42-题解 | #连续子数组的最大和(一)(二)#
连续子数组的最大和(二)
http://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21
题目描述:连续子数组的最大和(二)
输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,找到一个具有最大和的连续子数组。
1.子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组,那么返回其中长度最长的,该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1,不存在为空的子数组,即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算
题解:动态规划
动态转移方程
f(i) = arrar[i] ;i=0或者f(i-1)≤0
f(i) = arrar[i]+f(i-1) ;f(i-1)>0
- 首先使用cursum记录当前累计和,相当于f(i)
- 然后用result记录最大和
- 用四个指针记录位置,left和right为滑动指针,不停地改变对应位置;resleft和resright为结果指针,分别指向最大和的子数组的最最左边和最右边。
代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// write code here
if(array.size() == 1) return array;
vector<int> dp(array.size(),0);
int left = 0 ,right = 0;//滑动左右指针
int resleft = 0,resright = 0;//结果左右指针
int cursum = array[0];//当前累计和
int result = array[0];//最大值结果
for(int i =1;i<array.size();i++){
right++;//每一次循环,right自增指向下一个数值
if(cursum < 0) //累计和小于0,则cursum等于当前下标值
cursum = array[i],left = right;
else{ //大于等于0
cursum+=array[i];
}
//满足下面条件时,就可以移动结果左右指针了
if(cursum >= result){
result = cursum;
resleft = left;
resright = right;
}
}
// vector<int> resarr;
// for(int i =resleft;i<=resright;i++){
// resarr.push_back(array[i]);
// }
return vector<int>(array.begin()+resleft,array.begin()+resright+1);
}
};
题目描述:连续子数组的最大和(一)
输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。
题解:动态规划
动态转移方程
f(i) = arrar[i] ;i=0或者f(i-1)≤0
f(i) = arrar[i]+f(i-1) ;f(i-1)>0
- 首先使用cursum记录当前累计和,相当于f(i)
- 然后用result记录最大和
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
// 根据题意,数据范围n>1,所以不用考虑输入无效的情况
// 动态规划:使用临时变量
int curSum = 0;
int result = array[0];
for(int i =0;i<array.size();i++){
if(curSum <= 0)
curSum = array[i];
else
curSum +=array[i];
result = max(curSum, result);
}
return result;
//动态规划:使用数组
//动态转移方程:dp[i] = max(dp[i-1]+array[i],array[i])
// vector<int> dp(array.size(),0);
// int result = array[0];
// dp[0] = array[0];
// for(int i =0;i<array.size();i++){
// dp[i] = max(dp[i-1]+array[i],array[i]);
// result = max(result,dp[i]);
// }
// return result;
// int result = array[0];
// int temp = result;
// for(int i =1;i<array.size();i++){
// temp = max(array[i],temp+array[i]);
// result = max(temp,result);
// }
// return result;
}
};