# MCS
Maximum Consecutive Sum
## (1)無要求範圍
1. 動態規劃
轉移方程式
```cpp=
dp[i]=max(dp[i-1]+a[i],a[i]);
ma=(ma,dp[i]);
```
dp[i]為以a[i]為子序列末端最大連續元素和(對於每個a[i]可以是新的開頭或延伸前面的子序列,兩者取最大為此節點最佳解),在dp的時候要不斷更新最大值
最精簡寫法:
```cpp=
int dp=0,ma=INT_MIN;
for(int i=1;i<=n;i++){
cin >> v;
dp=max(dp+v,v);
ma=max(ma,dp);
}
```
2. 累積遍歷演算法
由上述dp狀態轉移可知dp[i]是由
```cpp=
1. dp[i-1]+v[i]
2. v[i]
```
取最大值而來,當2比較大時
```cpp=
dp[i-1]+v[i] < v[i]
```
同減v[i]
```cpp=
dp[i-1] < 0
```
代表前面的和小於0的時候dp[i]就是自己會是最佳解
所以我們可以推得code=
```cpp=
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;
}
```
<b>結論:當累積的前綴和小於0時,就把它歸零,因為對未來的結果沒有貢獻</b>
### 注意:此結論不可用於有限制數量和環狀陣列的題目
反例:
限制數量k:
[1 3 2 -3 999 -1]
k=3
最好[999]
環狀陣列:
[5 -3 5] 往後蓋...5 -3 5
最好[5,5]
## (2)最大連續元素和要求為K個
利用前綴合直接計算
```cpp=
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. 更新單調對列
```cpp=
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優化
```cpp=
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)
```cpp=
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個,因為不可以重複選
```cpp=
#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
Google Drive
Gist
Clipboard
Sign in with Wallet
