3689. Maximum Total Subarray Value I

題目 / Problem

中文 給你一個長度為 n 的整數陣列 nums 和一個整數 k。

你需要剛好選出 k 個非空的子陣列 nums[l..r](連續的一段)。子陣列可以重疊,而且同一個子陣列(相同的 l 和 r)可以被選不止一次。

一個子陣列 nums[l..r] 的值定義為:max(nums[l..r]) - min(nums[l..r])(這段裡的最大值減最小值)。

總值是所有被選子陣列的值的總和。請回傳能達到的最大總值。

English You are given an integer array nums of length n and an integer k.

You must choose exactly k non-empty subarrays nums[l..r] (contiguous segments). Subarrays may overlap, and the same subarray (same l and r) can be chosen more than once.

The value of a subarray nums[l..r] is max(nums[l..r]) - min(nums[l..r]). The total value is the sum of the values of all chosen subarrays. Return the maximum possible total value.

Constraints / 限制 - 1 <= n == nums.length <= 5 * 10^4 - 0 <= nums[i] <= 10^9 - 1 <= k <= 10^5

Worked example / 範例 nums = [1,3,2], k = 2 → output 4. Choose the whole array [1,3,2] twice. Each time value = 3 - 1 = 2. Total = 2 + 2 = 4.

名詞解釋 / Glossary

• 子陣列 / subarray:陣列中連續的一段元素,例如 [3,2] 是 [1,3,2] 的子陣列,但 [1,2] 不是(中間跳過了 3)。A contiguous slice of the array; elements must be adjacent.
• 全域最大值 / global maximum:整個陣列裡最大的數。The largest number in the whole array.
• 全域最小值 / global minimum:整個陣列裡最小的數。The smallest number in the whole array.
• 貪心 / greedy:每一步都直接選當下看起來最好的選項,而不嘗試所有組合。這題每次都選「值最大的子陣列」。A strategy that always picks the locally best option; here we always pick the most valuable subarray.
• 溢位 / overflow:計算結果太大,超出整數型別能表示的範圍,導致數值錯誤。需要用更大的型別(如 long long)。When a result exceeds the integer type's range and wraps to a wrong value; avoided by using a 64-bit type.

思路

最直接的想法是:枚舉所有可能的子陣列,算出每個子陣列的值(max - min),然後在這些值裡挑 k 個加起來最大。但子陣列有 O(n^2) 個,還要重複挑 k 次做選擇,這太慢也太複雜。關鍵的觀察是:我們可以重複選同一個子陣列,而且要選剛好 k 個。既然可以重複,那最聰明的做法就是找出「值最大的那一個子陣列」,然後把它選 k 次。那哪個子陣列的值最大呢?一個子陣列的值是它內部的最大值減最小值。範圍越大,內部的最大值只會更大或不變,最小值只會更小或不變,所以差距只會更大或不變。因此涵蓋整個陣列的子陣列 nums[0..n-1] 一定擁有最大的值,也就是全域最大值減全域最小值。把這個值乘上 k 就是答案。我們只需要掃一遍陣列找出最大與最小值即可。

The brute-force idea is to enumerate every subarray, compute each one's value (max − min), and pick the k largest. But there are O(n^2) subarrays, and that is both slow and overcomplicated. The key insight is that we may reuse the same subarray and must pick exactly k of them. So the smartest move is to find the single most valuable subarray and pick it k times. Which subarray is most valuable? A subarray's value is its internal max minus its internal min. Enlarging a subarray can only keep or raise its max and keep or lower its min, so the gap can only stay the same or grow. Therefore the subarray spanning the entire array, nums[0..n-1], always has the maximum value: the global maximum minus the global minimum. Multiply that by k and you have the answer. We only need one pass to find the array's max and min.

逐步走查 / Walkthrough

Input: nums = [1,3,2], k = 2. We scan once, tracking mx (running max) and mn (running min).

After the scan: mx = 3, mn = 1, so the best single subarray value is 3 - 1 = 2. Answer = (mx - mn) * k = 2 * 2 = 4. ✅ matches expected output.

Solution — C

// 演算法 / Algorithm:
//   最有價值的子陣列就是「整個陣列」,其值 = 全域最大 - 全域最小。
//   The most valuable subarray is the whole array: value = globalMax - globalMin.
//   重複選它 k 次即為答案 / Pick it k times: answer = (max - min) * k.
//   一次掃描找出最大最小,O(n) 時間 / One pass finds max & min in O(n).

long long maxTotalValue(int* nums, int numsSize, int k) {
    // 先把最大、最小都設成第一個元素 / Seed both max and min with the first element.
    // 因為陣列保證非空 (n >= 1),所以 nums[0] 一定存在 / Safe because n >= 1.
    int mx = nums[0];   // mx 記錄目前看過的最大值 / mx = largest seen so far
    int mn = nums[0];   // mn 記錄目前看過的最小值 / mn = smallest seen so far

    // 從第 2 個元素開始逐一比較 / Scan from the second element onward.
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > mx) mx = nums[i];   // 發現更大就更新 / update if a bigger value appears
        if (nums[i] < mn) mn = nums[i];   // 發現更小就更新 / update if a smaller value appears
    }

    // (mx - mn) 最大可達 10^9,再乘 k (最大 10^5) = 10^14,會超出 int 範圍。
    // (mx - mn) can be up to 10^9; times k (up to 10^5) = 10^14, which overflows 32-bit int.
    // 所以先轉成 long long (64 位元) 再相乘,避免溢位。
    // Cast to long long (64-bit) BEFORE multiplying to avoid overflow.
    return (long long)(mx - mn) * k;
}

Solution — C++

// 演算法 / Algorithm:
//   最有價值的子陣列是整個陣列,其值 = 全域最大 - 全域最小;選 k 次。
//   The best subarray is the whole array (max - min); choose it k times.
//   答案 = (max - min) * k,單次掃描 O(n)。
//   Answer = (max - min) * k, computed in a single O(n) pass.

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        // max_element / min_element 是 STL <algorithm> 提供的函式,
        // 它們各掃描一次區間,回傳指向最大/最小元素的「迭代器」(類似指標)。
        // max_element / min_element (from <algorithm>) each scan the range
        // and return an iterator (pointer-like) to the largest / smallest element.
        // 前面加 '*' 是「解參考」,取出迭代器指向的實際數值。
        // The leading '*' dereferences the iterator to get the actual value.
        int mx = *max_element(nums.begin(), nums.end());  // 全域最大 / global max
        int mn = *min_element(nums.begin(), nums.end());  // 全域最小 / global min

        // 轉成 long long 再乘,避免 (10^9 * 10^5) 溢位 32 位元 int。
        // Cast to long long before multiplying so 10^9 * 10^5 doesn't overflow int.
        return static_cast<long long>(mx - mn) * k;
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只需要把陣列從頭到尾掃一遍找出最大與最小值,n 是陣列長度;後面的乘法是常數時間。We scan the array once to find max and min (n = array length); the final multiplication is constant time. 主導成本是這趟掃描 / the scan dominates.
• Space: O(1) — 只用了 mx、mn 兩個額外變數,與輸入大小無關。Only two extra variables (mx, mn), independent of input size.

Pitfalls & Edge Cases

• 整數溢位 / Integer overflow:(mx - mn) 最大 10^9,乘上 k 最大 10^5,結果可達 10^14,遠超 32 位元 int 的上限(約 2.1 * 10^9)。必須在相乘之前轉成 long long,且回傳型別為 long long。Cast to 64-bit before the multiply, not after — casting the already-overflowed result is too late.
• 不要被 k 嚇到 / Don't overthink k:雖然要選 k 個子陣列,但因為允許重複,最佳策略就是把最好的選 k 次,不需要真的去枚舉 k 個不同子陣列。Because repetition is allowed, you never need to enumerate k distinct subarrays.
• 單一元素陣列 / Single-element array:若 n == 1,mx == mn,值為 0,答案是 0。程式碼自然處理:迴圈不執行,mx - mn = 0。Handled naturally — the loop body never runs and mx - mn = 0.
• 全部相同 / All equal elements:例如 [5,5,5],每個子陣列的值都是 0,答案為 0,符合公式。The formula gives 0, as expected.
• 空指標 / Pointer safety (C):用 nums[0] 當初始值前,題目保證 n >= 1,所以安全;若 n 可能為 0 則需先檢查。Seeding with nums[0] is safe only because the constraints guarantee n >= 1.