原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn3cg3/

解法一：

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];
        int max = cur;

        for (int i = 1 ; i < nums.length ; i++) {
            cur =  Math.max(cur,0) + nums[i];
            max = Math.max(max,cur);
        }

        return max;

    }
}

思路：动态规划

1，确定状态

2，找到转移公式

3，确定初始条件以及边界条件

4，计算结果。

这题是让求最大的连续子序和，如果不是连续的非常简单，只需要把所有的正数相加即可。但这里说的是连续的，中间可能掺杂负数，如果求出一个最大子序和在加上负数肯定要比原来小了。

遍历数组，每一次遍历的时候比较上一次记录的和，如和为负数，则重新在当前下标下重新计数，遍历结束后返回最后的结果即可。

解法二（java）：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1 ; i < len ; i++) {
            dp[i] = Math.max(dp[i-1],0) + nums[i];
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

思路：动态规划