LeetCode 最大子序和

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

子数组 是数组中的一个连续部分。

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
 

1 <= nums.length <= 105
-104 <= nums[i] <= 104

1、首先“最大和的连续子数组” 是一个逐渐累加的过程，这样我们很容易想到动态规划，即下一个状态由上一个状态决定

2、累加的过程就是要保证dp[i]不能小于零，也就是如果dp[i]小于零了，前面的累加就需要停止，从而重新累加，于是状态方程可以这样写：dp[i] = Math.max(dp[i - 1], 0) + nums[i];如果dp[i-1]小于零了，dp[i] 等于 nums[i]，也就是从新开始累加

3、因为要求最大的和，所以需要一个最大值进行记录

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