剑指 Offer 42. 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59h9mr

动态规划

public class Solution {
    public int maxSubArray(int[] nums) {
        // 放置 nums[0] 至 nums[i] 的最大和，最终结果为 dp 数组的最大值
        int[] dp = new int[nums.length];
        // 初使化，dp 第一项为 nums 的第一项
        dp[0] = nums[0];
        // 从第二项开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 如果前一位小于 0，说明是负贡献，不累加
            if (dp[i - 1] < 0) {
                dp[i] = nums[i];
            } else {
                // 否则累加
                dp[i] = nums[i] + dp[i - 1];
            }
        }
        Arrays.sort(dp);
        return dp[dp.length - 1];
    }
}

动态规划，不使用额外空间

public class Solution {
    public int maxSubArray(int[] nums) {
        // 优化点，不用额外空间，将 nums[0] 至 nums[i] 的最大和放在 nums[i]
        // 用于存放最大值 nums[0] 至 nums[i] 的最大值（累加之后）
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 累加，如果 nums[i - 1] 小于 0 则不累加
            nums[i] = nums[i] + Math.max(nums[i - 1], 0);
            // 刷新最大值
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}