动态规划—最大子序和问题 (LeetCode 53)

小半 • 2023年1月29日下午4:19 • 技术随笔 • 阅读 286

1.问题描述：

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

实例：

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

2.解题思路：

（1）定义数组元素的含义
按照题目所问的，设 dp[i] 的含义为：从nums[0]到nums[i]中最大和的连续子数组的和。

（2）求状态转换方程

上图是用蛮力法列出前4个状态的各个可能解。

通过上图我们得到了，状态转换方程：dp[i] = max(dp[i-1]+nums[i], nums[i])
按照这个状态转换方程推后面的状态看有没有错误：

dp[3-1]+nums[3]有：A2A3、A1A2A3 nums[3]有A3 。即dp[3]从A2A3、A1A2A3、A3 中选最大值，正确
dp[4-1]+nums[3]有：A3A4、A2A3A4、A1A2A3A4 nums[4]有A4 。即dp[4]从A3A4、A2A3A4、A1A2A3A4、 A4中选最大值，正确

（4）代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int len = nums.length;
        int[] dp = new int[len];
        //初始值
        dp[0] = nums[0];
        //状态转换：dp[i] = max(dp[i-1] + nums[i], nums[i])
        for (int i = 1; i < len; i++) {
            if (dp[i-1] > 0)
                dp[i] = dp[i-1] + nums[i];
            else
                dp[i] = nums[i];
            if (dp[i] > max)
                max = dp[i];
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        System.out.println(solution.maxSubArray(nums));
    }
}

注意：max(dp[i-1]+nums[i], nums[i])等价于当dp[i-1]>0时，dp[i-1]+nums[i]>nums[i]，取dp[i-1] + nums[i]。反之，取nums[i]

3.空间优化：

因为dp[i]只依赖于dp[i-1]和nums，而nums已知，所以，dp这个一维数组可以用一个变量代替，代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int len = nums.length;
        int dp = nums[0];  //dp代替原来一维数组的作用
        //状态转换：dp[i] = max(dp[i-1] + nums[i], nums[i])
        for (int i = 1; i < len; i++) {
            if (dp > 0)
                dp = dp + nums[i];
            else
                dp = nums[i];
            if (dp > max)
                max = dp;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        System.out.println(solution.maxSubArray(nums));
    }
}