Medium

题目描述

给你一个长度为 n 的整数数组 nums 和一个整数 k。

你需要恰好选择 k 个非空子数组 nums[l..r]。子数组可以重叠，同一个子数组（相同的 l 和 r）可以被选择多次。

子数组 nums[l..r] 的值定义为：max(nums[l..r]) - min(nums[l..r])。

总值是所有选择的子数组的值的和。

返回你能达到的最大可能总值。

示例 1：

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

解释：

一种最优方法是：

  • 选择 nums[0..1] = [1, 3]。最大值是 3，最小值是 1，值为 3 - 1 = 2。
  • 选择 nums[0..2] = [1, 3, 2]。最大值仍是 3，最小值仍是 1，所以值也是 3 - 1 = 2。

相加得到 2 + 2 = 4。

示例 2：

输入：nums = [4,2,5,1], k = 3
输出：12

解释：

一种最优方法是：

  • 选择 nums[0..3] = [4, 2, 5, 1]。最大值是 5，最小值是 1，值为 5 - 1 = 4。
  • 选择 nums[0..3] = [4, 2, 5, 1]。最大值是 5，最小值是 1，值也是 4。
  • 选择 nums[2..3] = [5, 1]。最大值是 5，最小值是 1，值仍是 4。

相加得到 4 + 4 + 4 = 12。

约束条件：

  • 1 <= n == nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= 10^5

提示： 选择整个子数组 k 次。

解题思路

这道题的关键洞察是：贪心策略 - 总是选择价值最大的子数组。

解题思路

  1. 暴力枚举所有子数组：遍历所有可能的子数组 [l, r]，计算每个子数组的价值 max - min。

  2. 贪心选择：由于同一个子数组可以被重复选择，我们应该贪心地选择价值最大的子数组。具体来说：

    • 找到价值最大的子数组，记为 maxValue
    • 答案就是 k * maxValue

  3. 优化思考：虽然可以用优先队列存储所有子数组价值然后取前k个，但由于可以重复选择，实际上只需要找到最大价值即可。

  4. 实现细节：

    • 双重循环遍历所有可能的 [l, r] 区间
    • 对于每个区间，维护当前的最大值和最小值
    • 更新全局最大价值

时间复杂度为 O(n²)，空间复杂度为 O(1)。这是最直观且高效的解法。

代码实现

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        int n = nums.size();
        long long maxValue = 0;
        
        for (int l = 0; l < n; l++) {
            int minVal = nums[l];
            int maxVal = nums[l];
            
            for (int r = l; r < n; r++) {
                minVal = min(minVal, nums[r]);
                maxVal = max(maxVal, nums[r]);
                maxValue = max(maxValue, (long long)(maxVal - minVal));
            }
        }
        
        return maxValue * k;
    }
};

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        max_value = 0
        
        for l in range(n):
            min_val = nums[l]
            max_val = nums[l]
            
            for r in range(l, n):
                min_val = min(min_val, nums[r])
                max_val = max(max_val, nums[r])
                max_value = max(max_value, max_val - min_val)
        
        return max_value * k

public class Solution {
    public long MaxTotalValue(int[] nums, int k) {
        int n = nums.Length;
        long maxValue = 0;
        
        for (int l = 0; l < n; l++) {
            int minVal = nums[l];
            int maxVal = nums[l];
            
            for (int r = l; r < n; r++) {
                minVal = Math.Min(minVal, nums[r]);
                maxVal = Math.Max(maxVal, nums[r]);
                maxValue = Math.Max(maxValue, (long)(maxVal - minVal));
            }
        }
        
        return maxValue * k;
    }
}

var maxTotalValue = function(nums, k) {
    const n = nums.length;
    let maxValue = 0;
    
    for (let l = 0; l < n; l++) {
        let minVal = nums[l];
        let maxVal = nums[l];
        
        for (let r = l; r < n; r++) {
            minVal = Math.min(minVal, nums[r]);
            maxVal = Math.max(maxVal, nums[r]);
            maxValue = Math.max(maxValue, maxVal - minVal);
        }
    }
    
    return maxValue * k;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 需要枚举所有可能的子数组
空间复杂度O(1) - 只使用常数额外空间