输入一个整形数组，数组中有正数也有负数。数组中的一个或连续的多个正数组成一个子数组。球所有子数组的和的最大值。 如输入{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},输出应该是18 这是在《剑指offer》上看到的题目，这道题可以在O(n)的时间复杂度内求解，而且这个问题可以是很多更加复杂问题的子问题。所以记录加深下印象。 分析： 以上面列出的{1,-2,3,10,-4,7,2,-5}来分析，可以这么想，从头开始遍历，当前面某几项的和是负数，需要舍弃前面的。 即从1开始，此时记录到的最大和为1,然后遍历到-2，因为1+(-2)<0，所以舍弃掉-2，然后继续向后分析，3>1,所以更新最大值为3，然后继续向后遍历，3+10=13,跟新最大值为13，13+(-4)=9,继续向后遍历。。。 即用两个中间变量来存储，一个用来存储遍历到当前项时最大的连续子数组之和（maxSum），另外一个用来存储包含当前项的最大子数组之和(curSum)，如果curSum>maxSum，那么用curSum更新maxSum，否则继续遍历。 代码如下：
f_validate=true;int getGreatestOfSubArray(int *datas,int length){if(datas==NULL|| length<=0){f_validate=false;return 0;}int curSum=0;int maxSum=0x80000000;//0x80000000是最小的负整数for(int i=0;i<length;i++){//如果当前和小于等于0，那么舍弃掉它，从数组中的当前项开始累加if(curSum<=0){curSum=datas[i];}else//否则当前和需要加上数组中的当前的项{curSum+=datas[i];}//每次计算一次当前的和后都需要更新最大和if(curSum>maxSum)maxSum=curSum;}return maxSum;}int main(){int datas[]={1,-2,3,10,-4,7,2,-5};int max；max=getGreatestOfSubArray(datas,sizeof(datas)/sizeof(datas[0]));std::cout<<max<<std::endl;return 0;}
之前还没注意，后来看了书之后发现可以用动态规划来分析这个问题： 设f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求的是max{f(i)},0<=i
/,int first,int last);int getGreatestSubOfArray(int * datas,int length){if(datas==NULL||length<=0) return -1;int curSum=0;int maxSum=0;//分割，，将数组以一个基准点分割成两部分，分别求两个部分的最大和，然后再求总的最大和for(int i=1;i<length-2;i++){curSum=getGreatest(datas,0,i)+getGreatest(datas,i+1,length-1);if(curSum>maxSum){maxSum=curSum;}}return maxSum;}/,int first,int last){if(datas==NULL||first<0||last<0||first>=last) return -1;int curSum=0;int maxSum=0;for(int i=first;i<last;i++)//从first到last依次遍历，计算相邻两项之间的差值，转换成了连续数组的最大和问题{if(curSum<=0)//如果当前和小于0，丢弃它{curSum=datas[i+1]-datas[i];}else//否则加上当前项{curSum+=datas[i+1]-datas[i];}if(curSum>maxSum)//更新最大值{maxSum=curSum;}}return maxSum;}int main(){int datas[]={1,4,5,2,3,1};int max=getGreatestSubOfArray(datas,sizeof(datas)/sizeof(datas[0]));std::cout<<max<<std::endl;return 0;}
没有人会帮你一辈子，所以你要奋斗一生。
