题目信息

题目地址：https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法一：动态规划

首先我们去划分一下子问题。整个数列的最大子序和，他是可能就等于n-1的最大子序和，它也可以是个新的值。至少是这两种情况

情况一：

1
2
3
[-1,3,1,-4,1]
当前数列的最大子序和就是4也就是(1,2)项。
它也是前n-1项的最大子序和

情况二：

1
2
3
[-1,3,1,-4,5]
当前数列的最大子序和是5也就是(4)项
而前n-1项的数列最大子序和还是4也就是(1,2)项

每次往后迭代一个值它的结果可能变化也可能不变化，这就是记录的点。我们算出当前最大的值然后与之前的result进行比较可能更新result也可能不变，进行下个迭代再次算当前最好的值再与result比较。

那么唯一的问题就是当前的最大值是怎么计算的，就是我们不是去暴力全部序列，而是跳过不必要的，即当前面sum为负的时候，即使后面有大的也没必要加上负的，也就是直接跳序列的首指针来达到减少遍历吃次数

1
2
3
4
5
6
[2,-1,-3,-4,7]
我们大概需要四个变量
result = 0 // 结果
i = 0 // 序列的首指针
j = 0 // 序列的尾指针
sum = 0 //当前序列和

但我们记录sum就代表i至j了，所以不用指针变量
代码如下：

1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
    //sum表示上一个最大子序和也就是dp[n-1]
    int sum = 0;
    int result = nums[0];
    for(int i = 0; i < nums.length; i++){
        sum = sum > 0 ? sum + nums[i] : nums[i];
        max = max > sum ? max : sum;
    }
    return max;
}

总结

这题的话虽然是简单但还是要点思考的，用到了动态与贪心的思想合起来减少了遍历一遍的次数。关于自顶向下的分治比较适合之后筹备的另一个系列，所以这里就不展开了