原题链接:Maximum Subarray

题目:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析:

  很显然,这是一道动态规划的题目,面对DP问题,那我们首先第一反应暴力求解(只是过程),暴力求解我们只需要将每个子段求和,然后更新max的值,就能很轻易求出题解,暴力求解代码如下:

int maxSubArray(int* nums, int numsSize){
    int i=0,j=0;
    int max=nums[0];
    for(i=0;i<numsSize;i++)
        for(j=0;j<=i;j++){
         int k,sum=0;
         for(k=j;k<=i;k++){
             sum+=nums[k];
         }
         if(max<sum) max=sum;
        }
      return max;
}

但是我们会发现,这样的话,算法复杂度在n2,那好,下一步,我们优化这个算法。我们用一个数代替一类数,那么,我们的算法复杂度就能降到n。具体怎么将呢;别急,看下面。

我们用f[i]代替所有以i结尾的子段,那么我们就用f[i]代替了这一类数(以i结尾的子段),那就是f[i],那么我们只需求出所有以i结尾的子段的和,遍历数组,求出最大值便是答案。那么我们继续发现还能优化,在所有以i结尾的子段里,有一个共同的值,那就是f[i],那么我们只需求出所有以i结尾的子段的但是不包括f[i]这个值的子段的最大值,最后加上f[i],对我们的最大值无影响;说了这么多,一张图了事:

最大子阵列(图1)

那么我们大体思想是max(f[0],f[1]........f[n-2],f[n-1])

那么代码如下:

    #define Max(a,b) ((a)>(b)?(a):(b))//宏定义返回a,b最大值
    int maxSubArray(int* nums, int numsSize){
        int maxn=nums[0],last=0,i=0;
        for(i=0;i<numsSize;i++){
            int now=Max(last,0)+nums[i];//计算除去f[i]以外所有以f[i]结尾的子段
            maxn=Max(maxn,now);
            last=now;//更新last
        }
        return maxn;
    }

以上就是题解,总的来说,这个DP算是偏简单的,思路也不是那么难,要是还有不懂,欢迎评论;