动态规划之最大子序和

示例：

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

解析:利用动态规划思想。假设i-1的最大子序和已经求出为dp[i-1],那么如果dp[i-1]小于0，第i个为结尾的最大子序和不如不加，因为前面i-1最大子序加出来都是负的，直接将nums[i]作为dp[i]。如果dp[i-1]大于0，那么证明前面的子序和不小，可以跟着一起做更大的。最大子序和要每次都和更新了的maxSum比大小。

代码:

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(dp[i-1] < 0){
                dp[i] = nums[i];
            }else{
                dp[i] = dp[i-1]+nums[i];//状态转移方程
            }
            maxSum = Math.max(maxSum,dp[i]);
        }
        return maxSum;
    }
}