LeetCode 第 4005 题：Maximum Total Subarray Value I 解题报告
题目描述
给定一个长度为 n 的整数数组 nums 和一个整数 k。你必须从 nums 中选择恰好 k 个非空子数组 nums[l..r]。子数组可以重叠，同一个子数组（相同的 l 和 r）可以被选择超过一次。
子数组 nums[l..r] 的值定义为：max(nums[l..r]) – min(nums[l..r])。
总值是所有被选子数组的值之和。返回你能实现的最大可能总值。
解题思路
关键观察
对于任何子数组 nums[l..r]，其值定义为 max(nums[l..r]) – min(nums[l..r])。但是，在整个数组中，最大值和最小值是固定的：
- 全局最大值：max(nums)
- 全局最小值：min(nums)
无论我们选择哪个子数组，其最大值都不会超过全局最大值，最小值都不会小于全局最小值。因此，对于任何子数组：
max(nums[l..r]) ≤ max(nums)
min(nums[l..r]) ≥ min(nums)
这意味着任何子数组的值都不会超过 (max(nums) – min(nums))。
最优策略
为了最大化总值，我们应该选择那些值最大的子数组。由于任何子数组的值最多为 (max(nums) – min(nums))，最优策略就是选择 k 个这样的子数组。因此，最大可能的总值为：
(max(nums) – min(nums)) * k
为什么这个策略是最优的？
算法实现
class Solution:
def maxTotalValue(self, nums: List[int], k: int) -> int:
max_num = max(nums)
min_num = min(nums)
return (max_num – min_num) * k
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历数组来找到最大值和最小值。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
示例验证
示例 1
输入：nums = [1,3,2], k = 2
- max(nums) = 3, min(nums) = 1
- 每个子数组的最大可能值 = 3 – 1 = 2
- 总值 = 2 * 2 = 4
- 输出：4
示例 2
输入：nums = [4,2,5,1], k = 3
- max(nums) = 5, min(nums) = 1
- 每个子数组的最大可能值 = 5 – 1 = 4
- 总值 = 4 * 3 = 12
- 输出：12
总结
这道题的关键在于理解子数组值的上限，并利用全局最大值和最小值来简化问题。通过观察可以发现，无论选择哪个子数组，其值都不会超过全局最大值与最小值的差。因此，最优策略就是选择 k 个这样的子数组，从而得到最大可能的总值。
