资源引用：

稀土掘金题目：

​​​​​​414.小U生活事件快乐值最大化

313. 0，1背包最大价值问题

448.最大连续子数组和问题

代码随想录文章：

代码随想录0，1背包问题

​​​​​​代码随想录0，1背包问题-2

豆包青训营官方题解文档：

448. 最大连续子数组和问题 - 飞书云文档 (larkoffice.com)

稀土掘金-414.小U生活事件快乐值最大化（414.小U生活事件快乐值最大化）

题目分析：

小U有n个事件可以分享，分享第i个时间需要花费ti的时间和hi的精力来编辑文章，并得到ai的快乐值，在限定总花费时间上限T和总花费精力上限H的前提下，求最多可以获得多少快乐值。

解题思路：

这个一个二维开销的01背包动态规划问题，

定义dp数组如下：

对dp[j][k]，表示在时间上限为j、精力上限为k的情况下，可分享事件的快乐值总和的最大值。

因此，初始化dp数组为new int[T+1][H+1]，采用倒叙遍历的方式进行求解如下。

public class Main {
    public static int solution(int n, int T, int H, int[] t, int[] h, int[] a) {
        int[][] dp = new int[T+1][H+1];
        for (int i = 0; i < n; i++) {
            for (int j = T; j >= t[i]; j--) {
                for (int k = H; k >= h[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-t[i]][k-h[i]] + a[i]);
                }
            }
        }
        return dp[T][H];
    }

    public static void main(String[] args) {
        System.out.println(solution(2, 2, 2, new int[]{1, 3}, new int[]{3, 1}, new int[]{3, 4}) == 0);
        System.out.println(solution(3, 5, 5, new int[]{2, 1, 3}, new int[]{1, 3, 2}, new int[]{10, 7, 8}) == 18);
        System.out.println(solution(1, 3, 3, new int[]{4}, new int[]{4}, new int[]{5}) == 0);
    }
}

稀土掘金-313. 0，1背包最大价值问题（313. 0，1背包最大价值问题）

题目分析：

关于经典的0，1背包问题笔者在这里不在赘述，推荐大家浏览代码随想录0，1背包问题理解题意。

解题思路：

在这里分别呈现3种基于java的解题思路，一律采用先遍历物品，再遍历背包的方式。

1. 常规二维数组的正序遍历法：

public class Main {
    public static int solution(int n, int[] weights, int[] values, int m) {
        int[][] dp = new int[n][m + 1];// java中新建数组会默认初始化每一位为0
        for (int j = 0; j <= m; j++) {
            if (j >= weights[0]) {
                dp[0][j] = values[0];
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j < weights[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }
            }
        }
        return dp[n - 1][m];
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[] { 2, 1, 3 }, new int[] { 4, 2, 3 }, 3) == 6);
        System.out.println(solution(4, new int[] { 1, 2, 3, 2 }, new int[] { 10, 20, 30, 40 }, 5) == 70);
        System.out.println(solution(2, new int[] { 1, 4 }, new int[] { 5, 10 }, 4) == 10);
    }
}

1. 简化统一的二维数组正序遍历法

在第1种方式中，我们还额外撰写了一个for循环进行使用第0个物品时（0~n-1共n个物品）的dp数组初始化。

为了简化统一，我们为dp数组额外增加1个第0行作为边界，遍历时i仍从1开始直至n共n个物品，利用Java初始化数组时自动初始化每个元素值为0的特性，使得后续的算式在对第一个物品（实际上是下标为0的物品）遍历时仍然符合含义。

此外，由于在weights数组和values数组中下标对应从0到n-1，故算式修改为dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);

public class Main {
    public static int solution(int n, int[] weights, int[] values, int m) {
        int[][] dp = new int[n+1][m+1];// 增设一个第0行作为边界
        for (int i = 1; i <= n; i++) {// 遍历第一至n个物品，实际上是i-1对应下标为0到n-1的物品
            for (int j = 0; j <= m; j++) {
                if (j < weights[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[]{2, 1, 3}, new int[]{4, 2, 3}, 3) == 6);
        System.out.println(solution(4, new int[]{1, 2, 3, 2}, new int[]{10, 20, 30, 40}, 5) == 70);
        System.out.println(solution(2, new int[]{1, 4}, new int[]{5, 10}, 4) == 10);
    }
}

1. 一维数组的倒叙遍历写法

首先推荐参考代码随想录0，1背包问题-2

观察dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i]);可知，第i行是直接利用第i-1行的数据。

为此可以通过使用一维数组（滚动数组）的方式，实现一种“直接拷贝”上一行数据的方式，从而简化dp数组。

定义dp[j]为容量上限为m的背包，所能装下物品的最高价值。

倒序遍历解释

采取倒叙遍历，以weights[i]为例：

1. dp[3] = dp[3-weights[i]] + values[i]
2. dp[2] = dp[2-weights[i]] + values[i]
3. dp[1] = dp[1-weights[i]] + values[i]

dp[3]依赖于dp[2]，dp[2]依赖于dp[1]，dp[1]依赖于dp[0]

显然，以dp[3]为例，使用的是未被更新过的，直接从上一层复制来的dp[2]，因此避免了第i个物品的重复使用。

正序遍历不可行性解释

当从左往右遍历即正序遍历时，会出现以下情况：

以weights[i]==1为例：

1. dp[1] = dp[1-weights[i]] + values[i]
2. dp[2] = dp[2-weights[i]] + values[i]
3. dp[3] = dp[3-weights[i]] + values[i]

……

显然，dp[1]使用的是未被更新过的dp[0]，而dp[2]使用的是已被更新过的dp[1]（即已经装入了第i个物品）

此时第i个物品被重复使用，而这显然是有悖于0，1背包问题的（每种物品只有一个）。

因此，采取一维滚筒数组时，必须使用倒叙遍历。

public class Main {
    public static int solution(int n, int[] weights, int[] values, int m) {
        int[] dp = new int[m+1];
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        return dp[m];
    }

    public static void main(String[] args) {
        System.out.println(solution(3, new int[]{2, 1, 3}, new int[]{4, 2, 3}, 3) == 6);
        System.out.println(solution(4, new int[]{1, 2, 3, 2}, new int[]{10, 20, 30, 40}, 5) == 70);
        System.out.println(solution(2, new int[]{1, 4}, new int[]{5, 10}, 4) == 10);
    }
}

稀土掘金-448.最大连续子数组和问题（448.最大连续子数组和问题）

题目分析：

首先厘清连续子数组的定义，是指所得的子数组的每一个元素在原数组中是两两相邻的。通过至多一次修改任一元素为x的操作，求解最大的连续子数组和。

解题思路：

• 首先，用一个resMax记录数组和的最大值，并初始化resMax=x
• 接着，使用双指针作为滑动窗口遍历全部连续子数组，

• • 使用一个tmpMinNum记录当前滑动窗口的最小元素，并初始化为窗口的第一个元素和x中的较小者。
  • 随着滑动窗口变动，更新窗口中的数组和，然后更新tmpMinNum
  • 通过tmpSum - tmpMinNum + x尝试做修改，并更新最大数组和resMax。

• 最终返回resMax。

public class Main {
    public static int solution(int n, int x, int[] a) {
        int resMax = x;
        for (int i = 0; i < n; i++) {
            resMax = resMax > a[i] ? resMax : a[i];
            int tmpSum = a[i];
            int tmpMinNum = a[i] < x ? a[i] : x;
            for (int j = i+1; j < n; j++){
                tmpSum += a[j];// 先求该窗口内的数组和
                tmpMinNum = tmpMinNum < a[j] ? tmpMinNum : a[j];// 然后更新该窗口内的最小元素
                resMax = tmpSum - tmpMinNum + x > resMax ? tmpSum - tmpMinNum + x : resMax;
            }
        }
        return resMax;
    }

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

补充修正：

由于原题题意有误，查看修正文档如下448官方题解，发现实际要求的是必须做一次x替换。所以代码修改如下：

public class Main {
    public static int solution(int n, int x, int[] a) {
        int resMax = x;
        int MinNum = a[0];//修改：记录全局最小元素，初始化为数组的首个元素
        for (int i = 0; i < n; i++) {
            resMax = resMax > a[i] ? resMax : a[i];
            int tmpSum = a[i];
            int tmpMinNum = a[i];// 修改：tmpMinNum仅记录当前连续子数组中的最小元素，不再考虑x
            for (int j = i+1; j < n; j++){
                tmpSum += a[j];// 先求该窗口内的数组和
                tmpMinNum = tmpMinNum < a[j] ? tmpMinNum : a[j];// 然后更新该窗口内的最小元素
                // 修改：由于tmpMinNum定义修改，所以增加tmpMinNum和x的关系判断
                if (tmpMinNum < x) resMax = tmpSum - tmpMinNum + x > resMax ? tmpSum - tmpMinNum + x : resMax;
                else resMax = tmpSum > resMax ? tmpSum : resMax;
            }
            MinNum = Math.min(MinNum, tmpMinNum);// 修改：记录全局最小元素
        }
        /*修改：
            由于题意要求必须做一次操作，所以当x比全局最小值还小时，
            先前得到的resMax是没有做x替换操作的结果，
            因此在此处将resMax修改为用x替换最小元素的结果，
            不论该最小元素是否在resMax对应的连续子数组中都不影响结果的正确性，因为resMax是求最大值。
        */
        if (MinNum > x) resMax = resMax - MinNum + x;
        return resMax;
    }

    public static void main(String[] args) {
        System.out.println(solution(16, 1, new int[]{17,17,4,13,11,3,6,13,7,13,13,13,6,16,6,11}) == 167);
    }
}