LeetCode 解題筆記：3689. Maximum Total Subarray Value I

作者：王一哲
日期：2026年6月9日


LeetCode 題目連結：3689. Maximum Total Subarray Value I

解題想法

中等難度的題目。題目給定一個陣列 $nums$，要從 $nums$ 之中選取 $k$ 個區間 $nums[l]$ 到 $nums[r]$，取區間的最大值、最小值相減，使 $k$ 個區間取出的相減結果加總最大。由於選取的區間可以重複，實際上這題就是取 $nums$ 的最大值 $imax$、最小值 $imin$，回傳 $(imax - imin) \times k$。

Python 程式碼

使用 max 及 min 取極值，速度較慢。Runtime: 15 ms, beats 48.00%. Memory: 26.40 MB, beats 88.80%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = min(nums), max(nums)
        return (imax - imin) * k

不使用 max 及 min 取極值，速度較快。Runtime: 11 ms, beats 69.60%. Memory: 25.75 MB, beats 100.00%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = float('inf'), -float('inf')
        for num in nums:
            if num < imin:
                imin = num
            if num > imax:
                imax = num
        return (imax - imin) * k

C++ 程式碼

使用 max_element 及 min_element 取極值。Runtime: 0 ms, beats 100%. Memory: 103.86 MB, beats 3.11%.

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        long long imax = *max_element(nums.begin(), nums.end());
        long long imin = *min_element(nums.begin(), nums.end());
        return (imax - imin) * k;
    }
};

不使用 max_element 及 min_element 取極值。Runtime: 0 ms, beats 100%. Memory: 103.60 MB, beats 96.89%.

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        long long imax = LLONG_MIN, imin = LLONG_MAX;
        for(auto num : nums) {
            if (num > imax) imax = num;
            if (num < imin) imin = num;
        }
        return (imax - imin) * k;
    }
};