Hard
题目描述
给定一个循环数组 nums 和一个整数 k。
将 nums 分割成至多 k 个子数组。由于 nums 是循环的，这些子数组可以从数组的末尾绕回到开头。
子数组的范围是其最大值和最小值之间的差值。分割的得分是所有子数组范围的总和。
返回所有循环分割中可能的最大得分。
示例 1：
输入：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。
示例 2：
输入：nums = [1,2,3,3], k = 1
输出：2
解释：
将 nums 分割为 [1, 2, 3, 3]。
[1, 2, 3, 3] 的范围是 max(1, 2, 3, 3) - min(1, 2, 3, 3) = 3 - 1 = 2。
得分是 2。
示例 3：
输入：nums = [1,2,3,3], k = 4
输出：3
解释：
与示例 1 相同，我们将 nums 分割为 [2, 3] 和 [3, 1]。注意 nums 可以分割成少于 k 个子数组。
约束条件：
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^9
- 1 <= k <= nums.length
解题思路
这道题需要我们在循环数组中找到最优的分割方案来最大化得分。关键观察是每个分割的得分等于该分割内的最大值减去最小值。
核心思路：
- 问题转化：我们可以将问题转化为选择哪些元素作为最大值（贡献+nums[i]），哪些作为最小值（贡献-nums[i]）
- 动态规划状态：使用 dp[picks][balance] 表示已经选择了 picks 个元素（包括最大值和最小值），当前最大值和最小值的数量差为 balance 时的最大得分
- 状态转移：对于每个位置，我们有三种选择：
- 选择当前元素作为某个分割的最大值（+nums[i]）
- 选择当前元素作为某个分割的最小值（-nums[i]）
- 跳过当前元素
- 循环处理：为了处理循环性质，我们将数组扩展一倍，然后在所有可能的起始位置运行DP
- 平衡约束：balance 范围限制在 [0, 2]，这确保了我们能够形成有效的分割
算法步骤：
- 对每个可能的起始位置运行DP
- 在DP过程中，跟踪已使用的picks数量和当前的balance
- 确保最终状态中最大值和最小值的数量相等（balance = 0）
- 返回所有可能结果中的最大值
代码实现
class Solution {
public:
long long maximumScore(vector<int>& nums, int k) {
int n = nums.size();
vector<int> extended = nums;
extended.insert(extended.end(), nums.begin(), nums.end());
long long result = 0;
for (int start = 0; start < n; start++) {
vector<vector<long long>> dp(2 * k + 1, vector<long long>(3, LLONG_MIN));
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
int idx = (start + i) % n;
vector<vector<long long>> newDp = dp;
for (int picks = 0; picks < 2 * k; picks++) {
for (int balance = 0; balance <= 2; balance++) {
if (dp[picks][balance] == LLONG_MIN) continue;
// Choose as max (+)
if (balance < 2) {
newDp[picks + 1][balance + 1] = max(newDp[picks + 1][balance + 1],
dp[picks][balance] + nums[idx]);
}
// Choose as min (-)
if (balance > 0) {
newDp[picks + 1][balance - 1] = max(newDp[picks + 1][balance - 1],
dp[picks][balance] - nums[idx]);
}
}
}
dp = newDp;
}
for (int picks = 2; picks <= 2 * k; picks += 2) {
result = max(result, dp[picks][0]);
}
}
return result;
}
};
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
n = len(nums)
result = 0
for start in range(n):
dp = [[-float('inf')] * 3 for _ in range(2 * k + 1)]
dp[0][0] = 0
for i in range(n):
idx = (start + i) % n
new_dp = [row[:] for row in dp]
for picks in range(2 * k):
for balance in range(3):
if dp[picks][balance] == -float('inf'):
continue
# Choose as max (+)
if balance < 2:
new_dp[picks + 1][balance + 1] = max(
new_dp[picks + 1][balance + 1],
dp[picks][balance] + nums[idx]
)
# Choose as min (-)
if balance > 0:
new_dp[picks + 1][balance - 1] = max(
new_dp[picks + 1][balance - 1],
dp[picks][balance] - nums[idx]
)
dp = new_dp
for picks in range(2, 2 * k + 1, 2):
result = max(result, dp[picks][0])
return result
public class Solution {
public long MaximumScore(int[] nums, int k) {
int n = nums.Length;
long result = 0;
for (int start = 0; start < n; start++) {
long[,] dp = new long[2 * k + 1, 3];
for (int i = 0; i <= 2 * k; i++) {
for (int j = 0; j < 3; j++) {
dp[i, j] = long.MinValue;
}
}
dp[0, 0] = 0;
for (int i = 0; i < n; i++) {
int idx = (start + i) % n;
long[,] newDp = new long[2 * k + 1, 3];
Array.Copy(dp, newDp, dp.Length);
for (int picks = 0; picks < 2 * k; picks++) {
for (int balance = 0; balance <= 2; balance++) {
if (dp[picks, balance] == long.MinValue) continue;
// Choose as max (+)
if (balance < 2) {
newDp[picks + 1, balance + 1] = Math.Max(
newDp[picks + 1, balance + 1],
dp[picks, balance] + nums[idx]
);
}
// Choose as min (-)
if (balance > 0) {
newDp[picks + 1, balance - 1] = Math.Max(
newDp[picks + 1, balance - 1],
dp[picks, balance] - nums[idx]
);
}
}
}
dp = newDp;
}
for (int picks = 2; picks <= 2 * k; picks += 2) {
result = Math.Max(result, dp[picks, 0]);
}
}
return result;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumScore = function(nums, k) {
const n = nums.length;
// Precompute ranges for all possible subarrays in the cyclic array
const range = Array(n).fill(0).map(() => Array(n).fill(0));
for (let i = 0; i < n; i++) {
let min = nums[i];
let max = nums[i];
for (let len = 1; len <= n; len++) {
const j = (i + len - 1) % n;
min = Math.min(min, nums[j]);
max = Math.max(max, nums[j]);
range[i][len - 1] = max - min;
}
}
let maxScore = 0;
// Try all possible starting positions and partition configurations
for (let start = 0; start < n; start++) {
// dp[pos][parts] = maximum score using 'parts' partitions ending at position 'pos'
const dp = Array(n + 1).fill(0).map(() => Array(k + 1).fill(-Infinity));
dp[0][0] = 0;
for (let pos = 1; pos <= n; pos++) {
for (let parts = 0; parts <= Math.min(pos, k); parts++) {
// Don't partition at this position
if (parts < k) {
dp[pos][parts] = Math.max(dp[pos][parts], dp[pos - 1][parts]);
}
// Partition at this position
if (parts > 0) {
for (let prevPos = parts - 1; prevPos < pos; prevPos++) {
if (dp[prevPos][parts - 1] > -Infinity) {
const segmentStart = (start + prevPos) % n;
const segmentLen = pos - prevPos;
dp[pos][parts] = Math.max(dp[pos][parts],
dp[prevPos][parts - 1] + range[segmentStart][segmentLen - 1]);
}
}
}
}
}
for (let parts = 1; parts <= k; parts++) {
maxScore = Math.max(maxScore, dp[n][parts]);
}
}
return maxScore;
};
复杂度分析
| 复杂度类型 | 值 |
|---|---|
| 时间复杂度 | O(n² × k) |
| 空间复杂度 | O(k) |
其中 n 是数组长度。时间复杂度来自于对每个起始位置运行DP，每次DP需要 O(n × k) 的时间。空间复杂度为 O(k)，用于存储DP状态。