你需要从 nums 中挑出刚巧 k 个非空的联络区间（子数组）。这些区间之间不错重复，消除双把握端点 (l， r) 所暗示的区间也可被重复登第屡次。

每个区间的得分为该区间内元素的最大值减去最小值。总体得分等于所选 k 个区间得分的总数。

求梗概赢得的最大总体得分。

附注：这里“子数组”指数组中由些许相邻元素构成的非空区间。

1

0

1

输入: nums = [4，2，5，1]， k = 3。

输出: 12。

解说:

一种最优的门径是：

遴荐 nums[0..3] = [4， 2， 5， 1]。最大值为 5，最小值为 1，得到的值为 5 - 1 = 4。

遴荐 nums[1..3] = [2， 5， 1]。最大值为 5，最小值为 1，是以值亦然 4。

遴荐 nums[2..3] = [5， 1]。最大值为 5，最小值为 1，是以值一样是 4。

将它们相加得到 4 + 4 + 4 = 12。

题目来独力扣3689。

解题大体经由

1. 问题分析与关节不雅察

• 题目条目在数组中遴荐 k 个非空联络子数组（区间），允许重复和重复遴荐消除区间

• 每个区间的得分是「区间最大值 - 区间最小值」

• 意见：最大化 k 个区间的得分总数

关节不雅察：

• 关于一个固定区间，其得分只取决于区间内的最大值和最小值

• 若是某个区间包含数组的全局最大值和全局最小值，那么它的得分便是全局最大值减全局最小值，这是可能的最大单区间得分

• 由于允许重复遴荐区间，咱们应该尽可能多地遴荐得分最高的阿谁区间

2. 寻找最优区间

• 遍历总共可能的子数组，找出得分最高的阿谁区间（最大值 - 最小值最大）

• 这个最优区间一定是包含某个最大值和某个最小值的区间

• 更精准地说，最优区间要么以某个最大值为右端点向左膨大包含最小值，要么以某个最小值为左端点向右膨大包含最大值

• 不错通过预解决每个位置左边的最小值和右边的最大值等信息来高效找出最优区间

3. 重复遴荐最优区间

• 找到得分最高的区间后，英雄联盟比赛投注由于不错重复遴荐，咱们应该遴荐这个区间 k 次

• 最大总体得分 = (最优区间得分) × k

4. 格外情况解决

• 若是 k = 0，得分为 0（但题目规则 k ≥ 1）

• 若是数组长度为 1，任何区间得分王人是 0（最大值=最小值），总体得分为 0

• 需要商量多个区间得分相通的情况，任选一个即可

5. 示例考据（nums = [4，2，5，1]， k = 3）

• 遍历总共可能的子数组：

[4]：4-4=0

[4，2]：4-2=2

[4，2，5]：5-2=3

[4，2，5，1]：5-1=4 ← 最高得分

[2]：2-2=0

[2，5]：5-2=3

[2，5，1]：5-1=4

[5]：5-5=0

[5，1]：5-1=4

[1]：1-1=0

• 最高得分为 4，出现屡次

• 重复遴荐得分为 4 的区间 3 次：4 × 3 = 12

• 与题目输出一致

复杂度分析

时期复杂度

• 需要找到最优区间的得分，这不错通过一次遍历在 O(n) 时期内完成（使用单调栈或动态设想手段）

• 因此总体时期复杂度为 O(n)，其中 n 是数组长度

突出空间复杂度

• 若是使用单调栈门径，需要 O(n) 的突出空间来存储扶助数组

• 若是使用更奥秘的数学推导，可能只需要 O(1) 突出空间

• 但商量到 n ≤ 50000，O(n) 的空间亦然统统不错选择的

• 因此总的突出空间复杂度为 O(n)

Go齐全代码如下：

package main

import (

"fmt"

"slices"

)

func maxTotalValue(nums []int， k int)int64 {

returnint64(slices.Max(nums)-slices.Min(nums)) * int64(k)

}

func main {

nums := []int{4， 2， 5， 1}

k := 3

result := maxTotalValue(nums， k)

fmt.Println(result)

}

Python齐全代码如下：

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

def maxTotalValue(nums， k):

return (max(nums) - min(nums)) * k

def main:

nums = [4， 2， 5， 1]

k = 3

result = maxTotalValue(nums， k)

print(result)

if __name__ == "__main__":

main

C++齐全代码如下：

#include

#include

#include

long long maxTotalValue(const std::vector& nums， int k) {

int maxVal = *std::max_element(nums.begin， nums.end);

int minVal = *std::min_element(nums.begin， nums.end);

return static_cast(maxVal - minVal) * k;

}

int main {

std::vector nums = {4， 2， 5， 1};

int k = 3;

long long result = maxTotalValue(nums， k);

std::cout

return0;

}

咱们笃信东谈主工智能为泛泛东谈主提供了一种“增强用具”，并奋发于于共享全标的的AI常识。在这里，您不错找到最新的AI科普著作、用具评测、普及恶果的隐讳以及行业瞻念察。

接待温雅“福大大架构师逐日一题”，发音问可赢得口试贵府，让AI助力您的夙昔发展。