原题链接：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;
}

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

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

那么我们大体思想是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算是偏简单的，思路也不是那么难，要是还有不懂，欢迎评论；