No.53 最大子序和 （Easy）

题目描述

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

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

示例2：
输入：nums = [-100000]
输出：-100000

思路

动态规划，令dp[i]表示以nums[i]结尾所能取到的连续子数组的最大和，有两种情况：

1. nums[i] >= dp[i - 1] + nums[i], 这种情况对应的是，之前的连续子数组的最大和为负数，在这种情况下，取nums[i]自身即最大和的连续子数组；例如[-1, -2, -3, 8], 对于nums[3], 只取自身才是最大的和；
2. nums[i] < dp[i - 1] + nums[i]， 例如[-1, -2, 4, 8], 对于nums[3], 取之前dp[2] + nums[3] 是最大的和， 因为dp[2]大于0.

代码

class Solution {
    public int maxSubArray(int[] nums) {
        // 初始化dp数组
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 对应思路中的两种情况，是只取自身还是取自身 + 之前的最大值
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        // 找到最大值
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i] > max) {
                max = dp[i]
            }
        }
        return max;
    }
}

以上代码遍历了两遍，其实可以一遍求出最大值，就是添加一个变量保存最大值即可, 我们也不需要保存每一个dp值，只需要当前值之前的dp值即可, 即求dp[i]时只需要知道dp[i - 1]即可。

class Solution {
    public int maxSubArray(int[] nums) {
        // 整个过程的最大值
        int maxValue = nums[0];
        // 以i结尾的最大值.
        int maxEndHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndHere = Math.max(nums[i], maxEndHere + nums[i]);
            maxValue = Math.max(maxValue, maxEndHere);
        }
        return maxValue;
    }
}