http://contest-hunter.org:83/contest/0x10「基本数据结构」例题/1201 最大子序和

题目

输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。

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

当m=4时，S=5+1-2+3=7 当m=2或m=3时，S=5+1=6

Input

第一行两个数n,m（n,m<=300000） 第二行有n个数，要求在n个数找到最大子序和

Output

一个数，数出他们的最大子序和

题解

贪心，$Ans[i]=S[i]-min{S[i..i-m]}$，可以用滑动窗口

还需要考虑开头什么都不减，可以用特殊元素

AC代码

#include <iostream> #include <algorithm> #include <cstdio> #include <queue> #define REP(r,x,y) for(register int r=(x); r<(y); r++) #define REPE(r,x,y) for(register int r=(x); r<=(y); r++) #ifdef sahdsg #define DBG(...) printf(__VA_ARGS__) #else #define DBG(...) (void)(0) #endif typedef long long LL; using namespace std; char ch; int si; template <class T> inline void read(T &k) { k=0; si=1; do ch=getchar(); while(!isdigit(ch) && ch!='-' ); if(ch=='-') {si=-1,ch=getchar();} while(isdigit(ch)) {k=k*10+ch-'0'; ch=getchar();} k*=si; } #define MAXN 1000007 LL arr[MAXN]; LL aw[MAXN], al=0, ar=1; int main() { #ifdef sahdsg freopen("in.txt", "r", stdin); #endif int n,m; read(n); read(m); LL ans=-0x3f3f3f3f3f3f3f3fLL; REPE(i,1,n) { read(arr[i]); // if(i>1) arr[i]+=arr[i-1]; } aw[0]=0; REPE(i,1,n) { while(ar>al && arr[i]<arr[aw[ar-1]]) ar--; aw[ar++]=i; while(ar>al && i-aw[al]>m) al++; printf("%lld\n", arr[aw[al]]); } return 0; }

 

转载于:https://www.cnblogs.com/sahdsg/p/10785913.html

相关资源：JAVA上百实例源码以及开源项目