你需要把这个轮回数组切成最多 k 段流畅子数组。因为数组是轮回的，这些子数组的切分允许从数组末尾不时“绕回”到起首，是以子数组仍然条款是流畅的元素序列（但不错超过末尾到起首的领域）。
对恣意一段子数组，先找出它内部的最大值和最小值，然后缱绻这段子数组的“领域”，界说为：
最大值 − 最小值
一次分裂的总得分等于整个子数组的领域之和。
在整个可能的轮回分裂形式中，你要复返梗概取得的最大总得分。
1
1
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。
题目来独力扣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段」「现时是否合手有/是否完成走动」（对应拆分最大值、最小值的收益）；
• 驱动景象：未切分的技巧收益为负无限（不测旨），IM体育只消驱动空景象正当。
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
f[j][1] = math.MinInt / 2
f[j][2] = math.MinInt / 2
}
f[0][0] = math.MinInt / 2
for i := l; 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
#include
#include
#include
using namespace std;
// 3573. 交易股票的最好时机 V
long long maximumProfit(vector& prices， int l， int r， int k) {
int n = prices.size;
// 创建dp数组: f[j][0]， f[j][1]， f[j][2]
vector> f(k + 2， vector(3));
// 驱动化
for (int j = 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
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& nums， int k) {
int n = nums.size;
int maxI = 0;
for (int i = 0; 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 nums = {1， 2， 3， 3};
int k = 2;
long long result = maximumScore(nums， k);
cout
return0;
}
咱们肯定东谈主工智能为庸碌东谈主提供了一种“增强器具”，并勤劳于共享全主义的AI学问。在这里，您不错找到最新的AI科普著述、器具评测、晋升成果的隐秘以及行业洞悉。
宽宥慈祥“福大大架构师逐日一题”IM体育官网，发音讯可取得口试费力，让AI助力您的将来发展。
开云app官方在线入口
备案号: