3381. 長度可被 K 整除的子數組的最大元素和

思路

因為要找到區間的和，所以考慮用前綴和，不過單用前綴和的複雜度依舊太高。
所以要利用題目給的另一個條件，也就是長度可以被k整除這件事情去優化。

當計算前綴和時，計算從i < j, nums[i] ~ nums[j]的總和，使用preSum[j] - preSum[i]，
因為我們要找最大的那個數值，因此要盡量讓preSum[i]小，preSum[j]大，
長度要被k整除，也就是說j % k = i % k。

$[1, 2, 3, 4, 5, 6, 7, 8], k = 2$
$[0, 1, 2, 3, 4, 5, 6, 7]$, 這是 index

拿上面的矩陣舉例，
當我想計算以nums[5]為終點，去找滿足題目條件的起點，
我所能參考的起點有nums[1], nums[3] 這兩個，肯定要選比較小的那一個。

遍歷到後面的nums[7]時，我能參考的起點有三，
nums[1], nums[3], nums[5]這三個，這時也是選最小的那一個。

在這裡nums[1], nums[3] 重複被考慮到最小值的計算裡面了，
因此在計算過程中記錄這個最小值，能增提高計算效率。

該怎麼紀錄？注意到nums[1], nums[3]之間距離都是k，% k = 1，
所以我們能透過餘數去判斷這個位置的數值，應該要被考慮到哪一部分的最小值當中。

因為前綴和只會用到最新的那位，能用一個變數代替。

程式碼

1. 前綴和

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> preSum(n + 1);
        for(int i = 0; i < n; ++i) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        // mn[i] = "% k = i 的最小前綴和"
        vector<long long> mn(k, LLONG_MAX / 2);
        // 需要計算 nums[i] ~ num[j], 且 (j - i) % k = 0;
        // 也就是 j % k = i % k;
        long long res = LLONG_MIN;
        for(int j = 0; j <= n; ++j) {
            int i = j % k;
            res = max(res, preSum[j] - mn[i]);
            // 盡量最小化 (不能獨立出來)
            mn[i] = min(mn[i], preSum[j]); 
        }
        return res;
    }
};

2. 空間優化

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        long long preSum = 0;
        // mn[i] = "% k = i 的最小前綴和"
        vector<long long> mn(k, LLONG_MAX / 2);
        // 需要計算 nums[i] ~ num[j], 且 (j - i) % k = 0;
        // 也就是 j % k = i % k;
        long long res = LLONG_MIN;
        for(int j = 0; j <= n; ++j) {
            int i = j % k;
            if(j) preSum += nums[j - 1];
            res = max(res, preSum - mn[i]);
            // 盡量最小化 (不能獨立出來)
            mn[i] = min(mn[i], preSum); 
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n + k)$, 能優化到 $O(k)$。