标签： 动态规划

目标

给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。

一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。

请你返回 平滑下降阶段 的数目。

示例 1：

输入：prices = [3,2,1,4]
输出：7
解释：总共有 7 个平滑下降阶段：
[3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1]
注意，仅一天按照定义也是平滑下降阶段。

示例 2：

输入：prices = [8,6,7,7]
输出：4
解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7]
由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。

示例 3：

输入：prices = [1]
输出：1
解释：总共有 1 个平滑下降阶段：[1]

说明：

• 1 <= prices.length <= 10^5
• 1 <= prices[i] <= 10^5

思路

求满足要求的子数组个数，要求子数组严格单调递减且相邻元素差为 1。

枚举右端点 r，假设满足条件的最小的左端点为 l，那么以 r 为右端点且满足条件的子数组个数为 r - l + 1。对于每一个 r，无需重复判断最小的 l，它可以从前一个状态转移过来，即如果 prices[r - 1] - prices[r] == 1 那么 l 仍是以 r - 1 为右端点且满足条件的最小左端点，否则 l = r。

代码

/**
 * @date 2025-12-15 9:10
 */
public class GetDescentPeriods2110 {

    public long getDescentPeriods(int[] prices) {
        long res = 0L;
        int l = 0;
        int n = prices.length;
        int prev = prices[0] + 1;
        for (int r = 0; r < n; r++) {
            if (prev - prices[r] != 1){
                l = r;
            }
            res += r - l + 1;
            prev = prices[r];
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k。你的任务是将 nums 分割成一个或多个 非空 的连续子段，使得每个子段的 最大值 与 最小值 之间的差值 不超过 k。

返回在此条件下将 nums 分割的总方法数。

由于答案可能非常大，返回结果需要对 10^9 + 7 取余数。

示例 1：

输入： nums = [9,4,1,3,7], k = 4
输出： 6
解释：
共有 6 种有效的分割方式，使得每个子段中的最大值与最小值之差不超过 k = 4：
[[9], [4], [1], [3], [7]]
[[9], [4], [1], [3, 7]]
[[9], [4], [1, 3], [7]]
[[9], [4, 1], [3], [7]]
[[9], [4, 1], [3, 7]]
[[9], [4, 1, 3], [7]]

示例 2：

输入： nums = [3,3,4], k = 0
输出： 2
解释：
共有 2 种有效的分割方式，满足给定条件：
[[3], [3], [4]]
[[3, 3], [4]]

说明：

• 2 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

划分数组 nums，使得每一个子数组的最大最小值之差不超过 k，求划分的总方法数。

定义 dp[i] 表示 [0, i] 满足条件的划分数，dp[i + 1] = Σdp[j] j∈[l, i]，l 是固定右端点后满足条件的最小下标。

枚举满足条件的最小下标时可以使用滑动窗口，使用单调栈来维护窗口的最大值与最小值。

代码

/**
 * @date 2025-12-09 9:38
 */
public class CountPartitions3578 {

    public int countPartitions(int[] nums, int k) {
        Deque<Integer> max = new ArrayDeque<>();
        Deque<Integer> min = new ArrayDeque<>();
        int mod = 1000000007;
        int n = nums.length;
        long[] dp = new long[n + 1];
        dp[0] = 1;
        int l = 0;
        long window = 0;
        for (int r = 0; r < n; r++) {
            while (!max.isEmpty() && max.peekLast() < nums[r]) {
                max.pollLast();
            }
            while (!min.isEmpty() && min.peekLast() > nums[r]) {
                min.pollLast();
            }
            max.offer(nums[r]);
            min.offer(nums[r]);
            int diff = max.peek() - min.peek();

            window += dp[r];
            while (l <= r && diff > k) {
                if (max.peek() == nums[l]) {
                    max.poll();
                }
                if (min.peek() == nums[l]) {
                    min.poll();
                }
                diff = max.peek() - min.peek();
                window -= dp[l++];
            }
            dp[r + 1] = window % mod;
        }
        return (int) (dp[n] % mod);
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k 。

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

示例 1：

输入： nums = [1,2], k = 1
输出： 3
解释：
子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

示例 2：

输入： nums = [-1,-2,-3,-4,-5], k = 4
输出： -10
解释：
满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

示例 3：

输入： nums = [-5,1,2,-3,4], k = 2
输出： 4
解释：
满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

说明：

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

思路

计算长度能被 k 整除的子数组的最大元素和。

核心点是维护同余前缀和的最小值。

也有网友使用滑窗加动态规划来做，滑窗计算 长度为 k 的子数组和，动态规划累加长度 m * k 的子数组和，这里使用了贪心策略，如果前面的子数组和小于 0，直接重置为 0。

代码

/**
 * @date 2025-11-27 9:06
 */
public class MaxSubarraySum3381 {

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE / 2);
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            int rem = i % k;
            res = Math.max(res, prefix[i] - minPrefix[rem]);
            minPrefix[rem] = Math.min(minPrefix[rem], prefix[i]);
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

说明：

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

思路

求整数数组中元素的最大和，要求和能被 3 整除。

• 如果和 sum % 3 == 1，可以去掉一个模 3 余 1 的最小元素，或者 两个模 3 余 2 的最小元素
• 如果和 sum % 3 == 2，可以去掉一个模 3 余 2 的最小元素，或者 两个模 3 余 1 的最小元素

代码

/**
 * @date 2025-11-23 20:46
 */
public class MaxSumDivThree1262 {

    public int maxSumDivThree(int[] nums) {
        int res = 0;
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        PriorityQueue<Integer> q2 = new PriorityQueue<>();
        for (int num : nums) {
            res += num;
            if (num % 3 == 1) {
                q1.offer(num);
            } else if (num % 3 == 2) {
                q2.offer(num);
            }
        }
        int mod = res % 3;
        if (mod == 1) {
            int sub = q1.size() == 0 ? 100000 : q1.peek();
            if (q2.size() > 1) {
                sub = Math.min(sub, q2.poll() + q2.poll());
            }
            res -= sub;
        } else if (mod == 2) {
            int sub = q2.size() == 0 ? 100000 : q2.peek();
            if (q1.size() > 1) {
                sub = Math.min(sub, q1.poll() + q1.poll());
            }
            res -= sub;
        }
        return res;
    }
}

性能

目标

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用 一次 。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

示例 1：

输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

说明：

• 1 <= power.length <= 10^5
• 1 <= power[i] <= 10^9

思路

有一个数组 power 表示咒语的伤害值，魔法师使用其中任意咒语后，就无法再使用伤害值 +1 +2 -1 -2 的咒语，每个咒语只能使用一次，求伤害值的最大值。

使用哈希表记录伤害值相同的和，创建新数组（不包含重复伤害值），根据伤害值排序。如果不选当前伤害值，状态可以从后面转移而来，如果选则从后面大于当前伤害值 + 2 的转移而来。

代码

/**
 * @date 2025-10-11 8:57
 */
public class MaximumTotalDamage3186 {

    public long maximumTotalDamage(int[] power) {
        Map<Integer, Long> sum = new HashMap<>();
        for (int i : power) {
            sum.merge(i, (long) i, Long::sum);
        }
        int n = sum.size();
        int[] powers = new int[n];
        int i = 0;
        for (Integer damage : sum.keySet()) {
            powers[i++] = damage;
        }
        Arrays.sort(powers);
        long[] mem = new long[n + 1];
        mem[n - 1] = sum.get(powers[n - 1]);
        for (int j = n - 2; j >= 0; j--) {
            int k = j;
            while (k < n && powers[k] - powers[j] <= 2) {
                k++;
            }
            mem[j] = Math.max(mem[j + 1], mem[k] + sum.get(powers[j]));
        }
        return mem[0];
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

说明：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

思路

有一个长度为 n 的数组，将 nums[i] 替换为 (nums[i] + nums[i + 1]) % 10，得到一个长度为 n - 1 的数组，反复执行这一过程，最终得到数组的三角和。

定义 dp[i] 表示 [i, n) 的三角和， 状态转移方程为 dp[i] = (dp[i] + dp[i + 1]) % 10。

代码

/**
 * @date 2025-09-30 8:44
 */
public class TriangularSum2221 {

    public int triangularSum(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                nums[j] = (nums[j] + nums[j + 1]) % 10;
            }
        }
        return nums[0];
    }
}

性能