LeetCode 3381 昨天Daily的dp+prefix sum題目

內文包括許多Latex語句，使用閱讀器等工具閱讀可能造成閱讀障礙。

題目描述

給定一個int陣列nums和一個整數k，找出nums中長度是k的倍數的子陣列的最大和。

思考過程

這裡有視覺化程式（程式有針對網頁性質調整，視覺過程以範例測資三為例），遇到疑問的時候他可能可以幫助你。

這題我一開始直接嘗試前綴和硬拆$O(n^2)$，但被狠狠TLE了。後來外加dp優化成$O(n)$

首先要建立前綴和

\[s[i] = \sum_{j=0}^{i-1} nums[j]\]

則i到j的子陣列和為s[j+1]-s[i]，並且所求為長度為k的倍數的最大和，所以可以由前k項的和加上之前最大的dp值（判斷最大值是$nk$的狀況，也就是使用dp[i-k]）來更新。

\[dp[i] = \begin{cases} \max(s[i+1]-s[i-k], s[i+1]-s[i-k]+dp[i-k]) & \text{if } i+1 > k \\ -\infty & \text{else} \end{cases}\]

因為$nums.length > k$，所以max值一定會被update到，不用擔心return$-\infty$的情況。

又可以知道

\[s[i+1]-s[i-k] < s[i+1]-s[i-k]+dp[i-k] \rightarrow dp[i-k] > 0\]

所以可以先計算s[i+1]-s[i-k]，再判斷dp[i-k]是否大於0來決定要不要加上。最後在每次計算出dp[i]後更新全體最大值。

實作時請特別注意i跟k範圍

完整程式碼

Accepted
Runtime: 7ms (Beats 79.87%)
Memory: 184.27MB (Beats 39.60%)

#define M -200000000000000
class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        vector<long long> dp(nums.size(), M);
        vector<long long> s(nums.size()+1);
        s[0] = 0;
        long long res = M;
        for(int i = 0; i < nums.size(); i++){
            s[i+1] = s[i]+nums[i];
            if(i+1 >= k){
                dp[i] = s[i+1] - s[i-k+1];
                if(i >= k && dp[i-k] > 0){
                    dp[i] += dp[i-k];
                }
                res = max(res, dp[i]);
            }
        }
        return res;
    }
};