【动态规划】连续子数组的最大和

动态规划（DP）：动态规划中每一个状态一定是由上一个状态推导出来的，有别于贪心，贪心是没有状态推导，而是从局部中选择最优的。

动态规划解题步骤

1：确定dp数组，dp[ i ]为包括下标 i 之前的最大连续子序列和。

2：确定状态转移方程，dp[ i ]有两个方向推出，dp[ i-1 ]+nums[ i ] 为加入当前连续子序列和，

num[ i ]为从头开始计算到下标为 i 的子序列和。

3：初始化dp数组，本题目可以看出dp[ i ]依赖于dp[ i-1 ],所以dp[ 0 ]是递推公司基础。

4：确定遍历顺序，本题需要从前往后遍历。

class Solution {
    public int maxSubArray(int[] nums) {
      
        int[] dp = new int[nums.length];
        dp[0] = nums[0];   //初始化dp
        int max = dp[0];   //作为一个中间变量输出最大值
        for(int i = 1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);  //状态转移方程
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}