剑指offer刷题记录
题目
连续子数组的最大和
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
分析：计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。通过分析我们发现，累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。class Solution {
public:
int FindGreatestSumOfSubArray(vector array) {
int cursum=array[0];
int maxsum=array[0];
for(int i=1;i<array.size();i++)
{
if(cursum<=0)
cursum=array[i];
else
cursum=cursum+array[i];
if(cursum>maxsum)
{
maxsum=cursum;
}
}
return maxsum;
}
};