changed 3 years ago  
Published Linked with GitHub

MCS

Maximum Consecutive Sum

(1)無要求範圍

  1. 動態規劃

轉移方程式



dp[i]=max(dp[i-1]+a[i],a[i]);
ma=(ma,dp[i]);

dp[i]為以a[i]為子序列末端最大連續元素和(對於每個a[i]可以是新的開頭或延伸前面的子序列,兩者取最大為此節點最佳解),在dp的時候要不斷更新最大值

最精簡寫法:







int dp=0,ma=INT_MIN;
for(int i=1;i<=n;i++){
    cin >> v;
    dp=max(dp+v,v);
    ma=max(ma,dp);
}
  1. 累積遍歷演算法

由上述dp狀態轉移可知dp[i]是由



1. dp[i-1]+v[i]
2. v[i]

取最大值而來,當2比較大時

dp[i-1]+v[i] < v[i]

同減v[i]

dp[i-1] < 0

代表前面的和小於0的時候dp[i]就是自己會是最佳解
所以我們可以推得code=







for(int i=1;i<=n;i++){
    dp[i]=dp[i-1]+v[i];
    ma=max(ma,dp[i]);  
    //要先取max避免只有負數的時候先被歸0就取不到負數了
    if(dp[i]<0) dp[i]=0;
}

結論:當累積的前綴和小於0時,就把它歸零,因為對未來的結果沒有貢獻

注意:此結論不可用於有限制數量和環狀陣列的題目

反例:

限制數量k:
[1 3 2 -3 999 -1]
k=3
最好[999]

環狀陣列:
[5 -3 5] 往後蓋…5 -3 5
最好[5,5]

(2)最大連續元素和要求為K個

利用前綴合直接計算










for(int i=1;i<=N;i++){
    cin >> v[i];
    sum[i]=sum[i-1]+v[i];
}
int ma=INT_MIN;
for(int l=0,r=k;r<=N;l++,r++){
    int cachesum=sum[r]-sum[l];
    ma=max(ma,cachesum);
}

(3)最大連續元素和要求最大為K個

  1. 計算前綴和
  2. 遍歷數列
  3. 利用set建立一個單調對列(set可自動排序方便找最小值)
  4. 維護單調對列(移除過期元素),對列內元素數最大為K個
  5. 在單調對列裡找出最小前綴和(*set.begin()),減掉當前前綴和就是以v[i]為結尾在往前K個內的最大連續元素和
  6. 更新最大值
  7. 更新單調對列








set<int> s;
s.insert(0);
 for(int i=1;i<=n;i++){
    if(i-k>0) s.erase(prefixsum[i-k-1]);
    cachesum=prefixsum[i]-*s.begin();
    ans=max(ans,cachesum);
    s.insert(prefixsum[i]);
  }

pq優化








priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0,0});
for(int i=1;i<=n;i++){
    while(!pq.empty() && pq.top().S<i-k) pq.pop();
    ans=max(ans,pre[i]-pq.top().F);
    pq.push({pre[i],i});
}

(4)環形陣列(circular subarray)

LeetCode:918. Maximum Sum Circular Subarray

solution 1

環形子陣列有兩種情況

  1. 最大連續元素和在頭尾內
  2. 最大連續完素和有包括頭尾

第一種就利用dp方法即可求得最大值,第二種利用總和減掉區間最小值(也適用dp方法)就是過頭尾的區間最大值

時間複雜度只有O(n)

































class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int maxnow=0;
        int minnow=0;
        int total=0;
        int maxans=INT_MIN;
        int minans=INT_MAX;
        int maxinteger=INT_MIN;
        
        for(int i=0;i<A.size();i++){
            maxinteger=max(maxinteger,A[i]);
            total+=A[i];
            
            //求區間最大值
            maxnow+=A[i];
            maxans=max(maxans,maxnow);
            if(maxnow<0) maxnow=0;
        
            //求區間最小值
            minnow+=A[i];
            minans=min(minans,minnow);
            if(minnow>0) minnow=0;
        
        }
        
        int ans=max(maxans,total-minans);
        if(maxinteger<0) return maxinteger;
        else return ans;

    }
};

有個例外:當A全為負數時,區間最小元素和會等於總和,這樣相減等於0,和區間最大取max會是0,所以應該要先判斷,如果全是負數就回傳陣列裡的最大值才是答案

solution 2

​​​​#優先對列

把[0,n-1]複製到[n,2n-1]並且把前綴和算出來,這樣就可以用上面(3)來計算,只是把k改成n個,因為不可以重複選
























#define pii pair<int,int>
#define F first
#define S second

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();
        vector<int> pre(2*n+1);
        for(int i=0;i<n*2;i++){
            pre[i+1]=pre[i]+nums[i%n];
        }
        int ans=-1e9;
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        pq.push({0,0});
        for(int i=1;i<=2*n;i++){
            while(!pq.empty() && pq.top().S<i-n) pq.pop();
            ans=max(ans,pre[i]-pq.top().F);
            pq.push({pre[i],i});
        }
        return ans;
    }
};

solution 3

​​​​#單調對列

solution 4

​​​​#線段樹

solution 5

​​​​#sparse table
Select a repo