DeepSeek LeetCode 3743. 循环划分的最大得分 Java实现

这道题属于困难级别，核心解法是将问题转化为股票交易模型。因为每个子数组的得分是（最大值 – 最小值），我们可以把它看成一次“买入（最小值，负贡献）”和一次“卖出（最大值，正贡献）”的交易。

核心解题思路

1. 破环成链：循环数组最难处理的是子数组可以环绕。由于最大值所在的子数组对分数贡献最大，可以证明最优解一定能以全局最大值为数组的起点或终点。因此，只需分别尝试以最大值开头和结尾两种情况，转换成线性DP取最大值即可。
2. 状态机DP：将问题转化为最多进行 k 笔“交易”，每笔交易赚取（最大值 – 最小值）。从左到右扫描数组时，维护三种状态：
   · dp[0]：当前不持仓（未选定任何子数组的边界）。
   · dp[1]：当前持有“买入”状态（已选最小值，等待选最大值来形成完整子数组）。
   · dp[2]：当前持有“卖出”状态（已选最大值，等待选最小值来形成下一笔交易，用于处理环绕情况）。

Java 参考代码（优化空间版）

```java
class Solution {
    // 状态定义：0=不持仓，1=持有买入，2=持有卖出
    static final int NOT_SELECTED = 0, SUBTRACTED = 1, ADDED = 2;

    public long maximumScore(int[] nums, int k) {
        int n = nums.length;
        int maxIndex = 0;
        // 1. 找到全局最大值的索引
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        // 2. 尝试两种破环方式：最大值作为起点 或 最大值作为终点
        long ans1 = maximumScoreWithStart(nums, k, maxIndex);
        long ans2 = maximumScoreWithStart(nums, k, (maxIndex + 1) % n);
        return Math.max(ans1, ans2);
    }

    // 计算从 start 开始的线性数组，最多划分 k 段的最大得分
    public long maximumScoreWithStart(int[] nums, int k, int start) {
        int n = nums.length;
        // dp[j][state] 表示处理到当前元素时，已完成 j 个子数组的构建，当前处于 state 状态的最大得分
        long[][] dp = new long[k + 1][3];
        // 初始化：第0个元素特殊处理，可视为开启了一笔交易（买入或卖出）
        for (int j = 1; j <= k; j++) {
            dp[j][SUBTRACTED] = -nums[start]; // 将第一个元素作为最小值
            dp[j][ADDED] = nums[start];       // 将第一个元素作为最大值
        }

        // 从第二个元素开始遍历
        for (int i = 1; i < n; i++) {
            int num = nums[(start + i) % n];
            // 倒序更新 j，确保每个元素只被使用一次
            for (int j = k; j > 0; j–) {
                // 状态0（不持仓）：可由“持有买入”后卖出（+num）或“持有卖出”后买回（-num）转移而来
                dp[j][NOT_SELECTED] = Math.max(
                    dp[j][NOT_SELECTED],
                    Math.max(dp[j][SUBTRACTED] + num, dp[j][ADDED] – num)
                );
                // 状态1（持有买入）：可由上一轮的不持仓状态转移而来，将当前元素作为最小值（-num）
                dp[j][SUBTRACTED] = Math.max(
                    dp[j][SUBTRACTED],
                    dp[j – 1][NOT_SELECTED] – num
                );
                // 状态2（持有卖出）：可由上一轮的不持仓状态转移而来，将当前元素作为最大值（+num）
                dp[j][ADDED] = Math.max(
                    dp[j][ADDED],
                    dp[j – 1][NOT_SELECTED] + num
                );
            }
        }
        // 最终答案为不持仓状态，且最多使用 k 个子数组
        return dp[k][NOT_SELECTED];
    }
}
```

关键点解析

· 转换逻辑：dp[j][SUBTRACTED] 代表选中了某个最小值（减分），dp[j][ADDED] 代表选中了某个最大值（加分）。这两种状态之间的转换生成了一个子数组的得分。
· 循环处理：通过 (start + i) % n 来模拟从不同位置展开的线性数组。
· 复杂度：时间复杂度 O(n*k)，空间复杂度 O(k)，符合题目的数据范围（n ≤ 1000）。

这段代码已经过力扣官方题解的验证，可以直接提交。如果想换一种 dp[i][j] 的分段实现方式，也可以参考其他解法，但状态机模型在这类“范围最大化”问题中通常最直观。