codeforce Problem D - Yet Another Yet Another Task
枚举、前缀和！！！！
这道题真的是个教训，要好看题，对题中所给数据敏感才行！！！！！！
题意：
给一个长n的数列a，有正有负有零。Alice选一闭区间[l,r],Bob拿走该区间中最大的元素a[j] (l<=j<=r)，
那么Alice的收获为a[l]+a[l+1]+a[l+2]+a[l+3]+.....+a[j-1]+a[j+1]+.....+a[r]
即去掉a[j]后区间的总和。特殊情况，如果l==r那么收获为零（Bob拿走了唯一的元素）
给你一个数组，求Alice能获得的最大收获。
数据范围： 1<=n<=1e5, -30<=a[i]<=30
闲谈：
这道题我拿到手，发现不能贪心，二分后就一股脑地铺在了动态规划上了！！！！
最后还被我总结出了一个错误的动态规划公式，关键是样例还都对，花了好大劲写下来。一提交WA。。嘿嘿。。。。。。。
分析：
我们观察数据，发现1<=n<=1e5,而a[i]却意外的小，仅仅是-30~~30。
那我们想想，如果首先我的数组里都是负数或零，那么我是不是最终对大收获一定是零。
也就是说，在本题中正数至关重要！！最大值一定是正数！如果最大值是负数或零那就没有意义了！
再结合我们看到的数据大小：-30<=a[i]<=30。
那么我们是否可以枚举最大值1~~30，枚举出当最大值是某特定正数时的最大收获。
最后再取max就行了！！
唉。。。我没有好好看题。要对数据敏感的。枚举是最基本的方法呀！！！！！！
那么接下来要解决的就是，我们美剧到最大数字b时，如何计算当b为最大值时，收获的最大值呢？
我们可以想象到我们最终所取到的区间应该是这样的：[x,x,x,x,b,x,x,x]
即以b为中心，向左右延伸所取到的总和最大的区间。注意这里x<=b
那么怎么去确定这个区间呢？我们分为两个方向去看这个问题：
要想取得[x,x,x,x,b,x,x,x]最大实际上就是取得最大的[x,x,x,x,b]与[b,x,x,x]
再把他们两个拼成一块！那么答案就形成了。
（这也是常见的思路和手段！）
而事实上这两个问题是相似的，我们看如何求出
以b为末尾的最大前缀和，且要保持该前缀中所有元素均<=b
我们想想如果[x4,x3,x2,x1,b]比[x3,x2,x1,b]大那么是不是意味着x4>0
同理如果[x5,x4,x3,x2,x1,b]<[x4,x3,x2,x1,b]那么是不是意味着x5<0
那我们再来判断一下：
如果[x7,x6,x5,x4,x3,x2,x1,b]<[x4,x3,x2,x1,b]时我们是不是可以判断[x7,x6,x5]一定小于零
ok问题的求解方法已经出来了！！
我们从左向右遍历元素，并计算累计元素和。如果累计元素和小于零那么我们零累计元素和cnt==0
为何如此？
假设我们计算累计元素和到x4时：
[x1,x2,x3,x4 。。。。。。。。x99,x100,b]
发现累计元素和x1+x2+x3+x4小于零，那么你猜最后的前缀还会不会有[x1,x2,x3,x4]呢？不会了！！！
所以，我们直接令累计前缀和为零再从x5开始计算就可以了！！！
或许你会问：也许x1+x2+x3+X4<0而x4>0呢?如果x4>0那么我们不是早在x3的时候就结束了吗？
在x1+x2+x3时候就已经<0了，然后我们就会从x4开始类及起！！
另外如果我们遇到x>b时也令前缀和cnt=0，因为我们的区间里绝不可能包含x>b所以一定在这之后
这样我们对数组[x1,x2,x3,b,x4,x5,b,x6,x7,x8,x9,b,b,x10,x11,b......]
从头到尾扫描一次，遇到b就将此时的前缀和记下来，这样我们可以得到所有b的最大前缀和！！！
同理，反向扫描一遍得到所有b的最大后缀和，这样我们一拼完美得到答案。
如此我们就求出了，当最大值是b时，所得到的最大收获。
干他个30次我们就得出正解了！！！！
代码如下，注意细节。
#include<iostream>;
#include<algorithm>;
#include<queue>;
using namespace std;
const int max_n = 1e5 + 100;
int a[max_n];
int ans[33];
int main() {
ios::sync_with_stdio(0);
int n;cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int b = 1;b <= 30;b++) {
deque<int> maxl;deque<int>maxr;
int max_l = 0;int max_r = 0;
for (int i = 1;i <= n;i++) {
if (a[i] > b) { max_l = 0;continue; }
else if (a[i] == b)maxl.push_back(max_l);
max_l += a[i];
if (max_l < 0) max_l = 0;
}
for (int i = n;i >= 1;i--) {
if (a[i] > b) { max_r = 0;continue; }
else if (a[i] == b)maxr.push_front(max_r);
max_r += a[i];
if (max_r < 0) max_r = 0;
}
for (int i = 0;i < maxl.size();i++)
ans[b] = max(ans[b], maxl[i] + maxr[i]);
}
int res = 0;
for (int i = 1;i <= 30;i++)
res = max(res, ans[i]);
cout << res << endl;
}唉！！！！！！我怎么没看见数据范围呢！！！！。。。。。。。烦烦烦！！！
