2026-03-30：循环划分的最大得分。用go语言，给你一个循环数组 nums 和一个整数 k。你需要把这个循环数组切成最多 k 段连续子数组。因为

福大大架构师每日一题

发布于 2026-03-31 21:31:44

690

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-03-30：循环划分的最大得分。用go语言，给你一个循环数组 nums 和一个整数 k。

你需要把这个循环数组切成最多 k 段连续子数组。因为数组是循环的，这些子数组的切分允许从数组末尾继续“绕回”到开头，所以子数组仍然要求是连续的元素序列（但可以跨越末尾到开头的边界）。

对任意一段子数组，先找出它里面的最大值和最小值，然后计算这段子数组的“范围”，定义为：

最大值 − 最小值

一次划分的总得分等于所有子数组的范围之和。

在所有可能的循环划分方式中，你要返回能够取得的最大总得分。

1 <= nums.length <= 1000。

1 <= nums[i] <= 1000000000。

1 <= k <= nums.length。

输入： nums = [1,2,3,3], k = 2。

输出： 3。

解释：

将 nums 划分为 [2, 3] 和 [3, 1]（环绕）。

[2, 3] 的范围是 max(2, 3) - min(2, 3) = 3 - 2 = 1。

[3, 1] 的范围是 max(3, 1) - min(3, 1) = 3 - 1 = 2。

总得分为 1 + 2 = 3。

题目来自力扣3743。

一、先明确题目核心规则

1. 循环数组：数组首尾相连，切分的子数组可以跨数组末尾+开头（比如数组[1,2,3,3]，子数组[3,1]是合法的）。
2. 切分要求：把循环数组切成最多k段连续子数组（可以切1~k段，不是必须切k段）。
3. 得分计算：每段子数组的得分 = 子数组最大值 - 子数组最小值；总得分 = 所有子段得分之和。
4. 目标：找到所有切分方式中最大的总得分。

二、解题核心突破口（关键转化）

这道题最核心的数学转化： 总得分 = 所有子段的(max-min)之和 = 整个数组的全局最大值出现的总次数 - 全局最小值出现的总次数 简化结论：要让总得分最大，只需要让全局最大值尽可能多的单独成段/拆分出来，全局最小值尽可能多的单独成段/拆分出来。

基于这个结论，解题第一步：

1. 找到数组中的全局最大值（记为maxVal），并记录它的任意一个位置maxI。
2. 循环数组的最优切分，一定是以全局最大值为起点/终点展开的（因为最大值是得分的核心来源）。

三、整体解题步骤（分4大阶段）

阶段1：找到全局最大值的位置

遍历整个数组，找到数值最大的元素，记录它的下标maxI。 ✅ 示例nums=[1,2,3,3]：全局最大值是3，位置是下标2或3。

阶段2：处理循环数组（破环成链）

循环数组无法直接计算，我们用破环法：把原数组复制一份拼接在后面，变成长度为2n的线性数组，这样所有循环连续子数组，都能在这个长数组中找到对应的连续片段。

阶段3：两种核心切分场景（覆盖所有循环最优解）

因为是循环数组，全局最大值maxI的位置决定了两种最优切分可能：

1. 场景1：全局最大值作为第一段的第一个元素，向后切分最多k段；
2. 场景2：全局最大值作为最后一段的最后一个元素，向后切分最多k段。

代码中分别计算这两种场景的最大得分：

• ans1：场景1的最大得分
• ans2：场景2的最大得分最终答案就是ans1和ans2中的较大值。

阶段4：动态规划计算单场景最大得分（核心计算过程）

针对每一种切分场景，用动态规划计算「最多切k段」的最大总得分，步骤如下：

1. 初始化DP状态 定义状态表示：
- • 用三维状态记录「切了j段」「当前是否持有/是否完成交易」（对应拆分最大值、最小值的收益）；
- • 初始状态：未切分的时候收益为负无穷（无意义），只有初始空状态合法。
2. 遍历数组元素，逐位更新DP 从指定起点开始，遍历n个元素（对应原数组长度），对每个元素：
- • 倒序遍历切分段数（从k+1段到1段，避免重复计算）；
- • 三种状态转移： ✅ 不操作：保持当前收益不变； ✅ 卖出：结束当前子段，结算收益（对应子段的max-min）； ✅ 买入：开始新的子段，记录成本。
3. 最终取值 遍历结束后，DP数组中存储的就是「最多切k段」能获得的最大总得分。

四、完整流程总览（结合示例）

以nums=[1,2,3,3]，k=2为例：

1. 找到全局最大值3，位置是下标2；
2. 破环成链得到[1,2,3,3,1,2,3,3]；
3. 计算两种场景：
- • 场景1：从下标2开始切分，最多2段；
- • 场景2：从下标3开始切分，最多2段；
4. 动态规划计算出两种场景的得分分别为2和3；
5. 取最大值3，就是最终答案。

五、时间复杂度 & 额外空间复杂度

1. 总时间复杂度

• 找全局最大值：遍历数组1次，复杂度O(n)；
• 两次动态规划计算：每次遍历n个元素，每层遍历k个段数，复杂度O(n*k)；
• 总时间复杂度：O(n*k)。

补充：n是数组长度，k是最大切分段数，n≤1000，完全满足题目要求。

2. 总额外空间复杂度

• 动态规划使用了二维数组(k+2) × 3，空间O(k)；
• 无其他大型辅助数组；
• 总额外空间复杂度：O(k)。

总结

1. 核心思路：利用全局最大/最小值转化得分，破环成链处理循环数组；
2. 计算方式：两种起点场景+动态规划求最大得分；
3. 时间复杂度：O(n*k)，空间复杂度：O(k)。

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

// 3573. 买卖股票的最佳时机 V
func maximumProfit(prices []int, l, r, k int)int64 {
    n := len(prices)
    f := make([][3]int, k+2)
    for j := 1; j <= k+1; j++ {
        f[j][1] = math.MinInt / 2
        f[j][2] = math.MinInt / 2
    }
    f[0][0] = math.MinInt / 2
    for i := l; i < r; i++ {
        p := prices[i%n]
        for j := k + 1; j > 0; j-- {
            f[j][0] = max(f[j][0], f[j][1]+p, f[j][2]-p)
            f[j][1] = max(f[j][1], f[j-1][0]-p)
            f[j][2] = max(f[j][2], f[j-1][0]+p)
        }
    }
    returnint64(f[k+1][0])
}

func maximumScore(nums []int, k int)int64 {
    n := len(nums)
    maxI := 0
    for i, x := range nums {
        if x > nums[maxI] {
            maxI = i
        }
    }

    ans1 := maximumProfit(nums, maxI, maxI+n, k)     // nums[maxI] 是第一个数
    ans2 := maximumProfit(nums, maxI+1, maxI+1+n, k) // nums[maxI] 是最后一个数
    return max(ans1, ans2)
}

func main() {
    nums := []int{1, 2, 3, 3}
    k := 2
    result := maximumScore(nums, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def maximumProfit(prices: List[int], l: int, r: int, k: int) -> int:
    n = len(prices)
    # 创建dp数组: f[j][0], f[j][1], f[j][2]
    f = [[0, 0, 0] for _ in range(k + 2)]
    
    # 初始化
    for j in range(1, k + 2):
        f[j][1] = -10**9  # 相当于 math.MinInt/2
        f[j][2] = -10**9
    f[0][0] = -10**9
    
    for i in range(l, r):
        p = prices[i % n]
        # 倒序遍历j
        for j in range(k + 1, 0, -1):
            f[j][0] = max(f[j][0], f[j][1] + p, f[j][2] - p)
            f[j][1] = max(f[j][1], f[j-1][0] - p)
            f[j][2] = max(f[j][2], f[j-1][0] + p)
    
    return f[k+1][0]

def maximumScore(nums: List[int], k: int) -> int:
    n = len(nums)
    maxI = 0
    for i, x in enumerate(nums):
        if x > nums[maxI]:
            maxI = i
    
    # nums[maxI] 是第一个数
    ans1 = maximumProfit(nums, maxI, maxI + n, k)
    # nums[maxI] 是最后一个数
    ans2 = maximumProfit(nums, maxI + 1, maxI + 1 + n, k)
    
    return max(ans1, ans2)

def main():
    nums = [1, 2, 3, 3]
    k = 2
    result = maximumScore(nums, k)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 3573. 买卖股票的最佳时机 V
long long maximumProfit(vector<int>& prices, int l, int r, int k) {
    int n = prices.size();
    // 创建dp数组: f[j][0], f[j][1], f[j][2]
    vector<vector<int>> f(k + 2, vector<int>(3));

    // 初始化
    for (int j = 1; j <= k + 1; j++) {
        f[j][1] = INT_MIN / 2;
        f[j][2] = INT_MIN / 2;
    }
    f[0][0] = INT_MIN / 2;

    for (int i = l; i < r; i++) {
        int p = prices[i % n];
        for (int j = k + 1; j > 0; j--) {
            f[j][0] = max({f[j][0], f[j][1] + p, f[j][2] - p});
            f[j][1] = max(f[j][1], f[j-1][0] - p);
            f[j][2] = max(f[j][2], f[j-1][0] + p);
        }
    }

    return (long long)f[k+1][0];
}

long long maximumScore(vector<int>& nums, int k) {
    int n = nums.size();
    int maxI = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > nums[maxI]) {
            maxI = i;
        }
    }

    long long ans1 = maximumProfit(nums, maxI, maxI + n, k);     // nums[maxI] 是第一个数
    long long ans2 = maximumProfit(nums, maxI + 1, maxI + 1 + n, k); // nums[maxI] 是最后一个数

    return max(ans1, ans2);
}

int main() {
    vector<int> nums = {1, 2, 3, 3};
    int k = 2;
    long long result = maximumScore(nums, k);
    cout << result << endl;

    return0;
}