53.最大子序和

题目描述

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

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

  题解

  动态规划

  此题在遍历每个元素时都要考虑当前值与之前所有值之和的最大值。也就是说当遍历到某个元素时，在另一个平行数组中放置截止到这个元素的最大和。如何判断很简单，因为只需要考虑这个元素与之前的和即可，即cur=num[i]和preSum(i-1)。

通过运算Math.max(cur, cur+preSum(i-1))就可以求出。文字描述就是之前的值加上当前值如果还没有当前值大，那就丢弃之前的值保留当前值，否则就保留之前的值加上当前值的和。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;
        int maxSum = nums[0];
        for (int cur : nums) {
            pre = Math.max(cur, pre + cur);
            maxSum = Math.max(pre, maxSum);
        }
        return maxSum;
    }
}