描述

輸入一個(gè)長(zhǎng)度為n的整數(shù)序列，從中找出一段不超過M的連續(xù)子序列，使得整個(gè)序列的和最大。

例如?1，-3,5,1，-2,3

當(dāng)m=4時(shí)，S=5+1-2+3=7
當(dāng)m=2或m=3時(shí)，S=5+1=6

輸入格式

第一行兩個(gè)數(shù)n,m
第二行有n個(gè)數(shù)，要求在n個(gè)數(shù)找到最大子序和

輸出格式

一個(gè)數(shù)，數(shù)出他們的最大子序和

測(cè)試樣例1

輸入

6 4?
1 -3 5 1 -2 3

輸出

7

備注

數(shù)據(jù)范圍：
100%滿足n,m<=300000

題解

我們由題設(shè)f[i]為i位置最大子段和，得到狀態(tài)轉(zhuǎn)移方程f[i] = max(f[i - 1],sum[i] - sum[k]); ?【i - k <= m】 很明顯這樣做是O(n ^ 2) 對(duì)于求sum[i] - sum[k]的最大值，我們可以用單調(diào)隊(duì)列優(yōu)化
單調(diào)隊(duì)列 單調(diào)隊(duì)列，顧名思義，就是單調(diào)的隊(duì)列，用以O(shè)(1)求最值 單調(diào)隊(duì)列用雙向隊(duì)列維護(hù)，隊(duì)首是最值【假設(shè)是最大】 每次我們向隊(duì)尾插入一個(gè)元素時(shí)，我們?nèi)絷?duì)尾的元素比它要小就將他刪除，直至隊(duì)列為空或者隊(duì)尾元素大于插入 元素，再將其插入 例如5 3 1，我們要插入4 檢查1 < 4，隊(duì)列變?yōu)? 3 檢查3 < 4，隊(duì)列變?yōu)? 檢查5 > 4，隊(duì)列變?yōu)? 4 插入完成
你會(huì)發(fā)現(xiàn)這樣的操作能滿足隊(duì)列一定單調(diào)，而隊(duì)首就是我們要的值 但注意隨著時(shí)間的推移，隊(duì)首元素可能“過時(shí)”，就是超出了我們所規(guī)定的范圍，這個(gè)時(shí)候就刪除隊(duì)首，直至滿足范圍 由于每個(gè)元素最多進(jìn)隊(duì)出隊(duì)一次，所以總復(fù)雜度O(n)
那么這題就好做了，我們用一個(gè)單調(diào)隊(duì)列維護(hù)前m個(gè)sum值，每次只用O(1)就可以轉(zhuǎn)移方程 復(fù)雜度O(n)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long int #define REP(i,n) for (int i = 1; i <= (n); i++) #define fo(i,x,y) for (int i = (x); i <= (y); i++) #define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next) using namespace std; const int maxn = 300005,maxm = 100005,INF = 1000000000; inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag; } int n,m,q[maxn],head,tail,sum[maxn],f[maxn]; int main() {n = read(); m = read();REP(i,n) sum[i] = sum[i - 1] + read();head = tail = 0; q[head] = 0;for (int i = 1; i <= n; i++){while (i - q[head] > m) head++;f[i] = max(f[i - 1],sum[i] - sum[q[head]]);q[++tail] = i;while (tail > head && sum[q[tail]] < sum[q[tail - 1]]) q[tail - 1] = q[tail],tail--;}cout<<f[n]<<endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/8282827.html

總結(jié)

以上是生活随笔為你收集整理的tyvj1305 最大子序和 【单调队列优化dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。