对于一个区间 [l,r]，我们取 m=⌊(l+r)/2⌋，对区间 [l,m] 和 [m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。这个时候考虑如何通过 [l,m] 区间的信息和 [m+1,r]区间的信息合并成区间 [l,r][l,r] 的信息。最关键的两个问题是：

要维护区间的哪些信息呢？
如何合并这些信息呢?

对于一个区间 [l,r]，我们可以维护四个量：

Sum 表示 [l,r] 内以 l 为左端点的最大子段和
rSum 表示 [l,r] 内以 rr为右端点的最大子段和
mSum 表示 [l,r] 内的最大子段和
iSum 表示 [l,r] 的区间和

以下简称 [l,m] 为 [l,r] 的「左子区间」，[m+1,r] 为 [l,r] 的「右子区间」。考虑如何维护这些量呢?（如何通过左右子区间的信息合并得到 [l,r] 的信息）？

对于长度为 1 的区间 [i,i]，四个量的值都和 nums[i] 相等。对于长度大于 1 的区间：

首先最好维护的是 iSum，区间 [l,r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
对于 [l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
对于 [l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
当计算好上面的三个量之后，就很好计算 [l,r] 的 mSum 了。我们可以考虑 [l,r] 的 mSum 对应的区间是否跨越 m——
- 可能不跨越 m，也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和「右子区间」的 mSum 中的一个；
- 也可能跨越 m，可能是「左子区间」的 rSum 和「右子区间」的 lSum 求和。
- 最后三者取大。

这样问题就得到了解决。

class Solution {
    public class Status {
        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {
            return new Status(a[l], a[l], a[l], a[l]);
        }
        int m = (l + r) >> 1;
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}

3. 动态规划+临时变量

动态规划解析：

状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
- 为何定义最大和 dp[i] 中必须包含元素 nums[i] ：保证 dp[i] 递推到 dp[i+1] 的正确性；如果不包含 nums[i]，递推时则不满足题目的 连续子数组 要求。
- 设 dp 为一维数组，其中 dp[i] 的值代表前i个数字组成数组的最大子数组和。
转移方程：若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
- 当 dp[i−1]>0 时：执行 dp[i]=dp[i−1]+nums[i] ；
- 当 dp[i−1]≤0 时：执行 dp[i]=nums[i] ；
初始状态： dp[0] = nums[i]；，即以 nums[0] 结尾的连续子数组最大和为 nums[0] 。
返回值：返回 dp 列表中的最大值，代表全局最大值。

4. 动态规划+原地修改

空间复杂度降低：

由于 dp[i] 只与 dp[i-1] 和 nums[i] 有关系，因此可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。
由于省去 dp 列表使用的额外空间，因此空间复杂度从 O(N) 降至 O(1) 。

复杂度分析：

时间复杂度 O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
空间复杂度 O(1) ： 使用常数大小的额外空间。

2 礼物最大价值

剑指 Offer 47. 礼物的最大价值https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

1. 动态规划+二维数组

package jzof.Day09;

/**
 * @author ahan
 * @create_time 2021-11-11-11:45 上午
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 */
public class _47 {
    public static void main(String[] args) {
        int [][] nums = new int[][]{
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(new _47().maxValue(nums));
    }
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(dp[i][j]+"\t");
            }
            System.out.println("  ");
        }
        return dp[m-1][n-1];
    }
}

居然和大佬实现的思路方法一毛一样哈哈哈~ 不过大佬是原地修改。。。

空间效率上也差的不多~

复杂度分析：

时间复杂度 O(MN) ： M,N 分别为矩阵行高、列宽；动态规划需遍历整个 grid 矩阵，使用 O(MN) 时间。
空间复杂度 O(1) ： 原地修改使用常数大小的额外空间。

2. 多开一行一列0 优化代码

public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        //dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
        int[][] dp = new int[row + 1][column + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= column; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[row][column];
    }

码农公寓

动态规划

1 连续子数组最大和

1. 暴力法

2. 分治法（官方题解--线段树）

3. 动态规划+临时变量

4. 动态规划+原地修改

2 礼物最大价值

1. 动态规划+二维数组

2. 多开一行一列0 优化代码

相关文章