网站建设基础 ppt,济南网上房地产,横向网站源码,wordpress侧边栏加载js题干#xff1a;
输入一个长度为n的整数序列#xff0c;从中找出一段不超过M的连续子序列#xff0c;使得整个序列的和最大。 例如 1#xff0c;-3,5,1#xff0c;-2,3 当m4时#xff0c;S51-237 当m2或m3时#xff0c;S516
输入格式
第一行两个数n,m 第二行有n个数
输入一个长度为n的整数序列从中找出一段不超过M的连续子序列使得整个序列的和最大。 例如 1-3,5,1-2,3 当m4时S51-237 当m2或m3时S516
输入格式
第一行两个数n,m 第二行有n个数要求在n个数找到最大子序和
输出格式
一个数数出他们的最大子序和
提示
数据范围 100%满足n,m300000
样例数据
输入样例 #1输出样例 #1 6 4
1 -3 5 1 -2 3 7
解题报告
dp[i]表示到第i个数的不超过m的最大连续子段和,sum[i]表示i的前缀和 dp[i]max(sum[i]-sum[k])i k i-m,所以要找在窗口内的最小的sum[k]因此用单调队列优化一下。
然后这里dp不用开数组了你直接拿个ans记录一下最大值就行因为更新过一次之后就没有用过。当然你也可以最后扫一遍dp数组输出最大值 注意你要用的是sum[i]-sum[ (i-m1) -1]所以你第一个while要写成i-m而不是i-m1。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 3e5 5;
ll a[MAX],sum[MAX],ans;
int n,m;
dequell dq;
int main()
{ans -99999999;cinnm;for(int i 1; in; i) scanf(%lld,ai),sum[i] sum[i-1] a[i];dq.push_back(0); for(int i 1; in; i) {while(!dq.empty() dq.front() i-m) //注意这里不能用dq.size()判断因为只能说明双端队列中有m个元素但是不能证明就是连续的m个有可能队首元素是a[1]呢因为有可能中间的元素都在下一个while中被pop了 dq.pop_front();while(!dq.empty() sum[dq.back()] sum[i]) dq.pop_back();dq.push_back(i); ans max(sum[i] - sum[dq.front()],ans);}printf(%lld\n,ans);return 0 ;
}
/*
6 4
1 -3 5 1 -2 3
1 -2 3 4 2 5
*/
在此处交题http://www.joyoi.cn/problem/tyvj-1305
