最大子序和 —— 动态规划解法

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

示例:

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

思路：

我的思路就是正常从左往右走几遍就会发现他的规律

定义两个值：一个当前的子序列的和 sum，一个最大和 max。

设定初始的 sum = 0，max = num[0]。

1 从 -2 开始，sum = -2 ，我们会发现，负数加上正数不会比这个正数大，所以 -2+1 < 1 。那么这个负数就没有存在的意义了，抛弃。

　　→ sum = -2，max = -2

2 继续从 1 开始，sum = 1，1 + (-3) 看不出什么，我们把这个和记录下来，也就是 -2 ，是个负数。

　　→ sum = -2， max = -2

3 继续往后 4，我们又回到了类似第 1 步的问题，后面这个数是正数，肯定从正数开始，和才会越来越大，所以，抛弃 -2， 选择4，sum = 4 。

　　→ sum = 4， max = 4

4 继续往后-1，我们记录当前的和，但是这个和小于max，所以不更新max。

　　→ sum = 3，max = 4

5 继续往后2，当前的和大于max，更新max。

　　→ sum = 5，max = 5

6 继续往后1，同5。

　　→ sum = 6，max = 6

7 继续往后-5，同4。

　　→ sum = 1，max = 6

..... 

最后得出最大的子序列和为 6 。

现在我们是不是发现了很多规律~

注意：1 当只有一个数的时候，最大的就是这个数。

　　　2 如果序列里有大于0 的数，那么最大子序列的开头一定是大于0的数。

我的代码：

    public static int maxSubArray(int[] nums) {
        int sum = 0;
        int ans = nums[0];
        for (int i = 0; i < nums.length; i++) {
　　　　　　　// 这个的意思也就是sum + nums[i] > nums[i]，也就是sum > 0
            if (sum > 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
　　　　　　　// 如果当前sum更大，则更新
            if (sum >= ans) {
                ans = sum;
            }
        }
        return ans;
    }