连续子数组的最大和

一、思路

此题采用动态规划的方式求解，在此之前我们要先了解何为动态规划，以及采用动态规划所要进行的步骤。

动态规划：动态规划在寻找有很多重叠子问题的情况的最佳解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被储存，从简单的问题直到整个问题都被解决。因此，动态规划储存递迴时的结果，因而不会在解决同样的问题时花费时间。

动态规划的三个步骤：

• 建立状态转移方程
   
• 缓存并复用以往结果
   
• 按顺序从小往大算

对照本题三个步骤分别为

1.建立状态转移方程。

当 ddp[i−1]>0 时：执行 dp[i] = dp[i-1] + nums[i]
当 dp[i−1]≤0 时：执行 dp[i] = nums[i]

至于第2点第3点，采用for循环并将下标从小到大即可实现

二、代码 

代码已经标记了必要的步骤

class Solution {
    public int maxSubArray(int[] nums) {

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){// 2 3
            if(dp[i - 1] < 0){
                dp[i] = nums[i]; //1
            }else{
                dp[i] = dp[i - 1] + nums[i];//1
            }      
        }
        int result = Integer.MIN_VALUE;
        for(int value : dp){
            if(result < value){
                result = value;
            }
        }

        return result;

    }
}