贪心
由题可得，对于k的选择一定是单调递增的，对于前面选定的k后面选的k必须大于之前选的才会发生新的变化，因此k的选择其实是一个单调栈，由前缀和组成
我们要想最后的结果最大，则k值一定要尽可能的高，例如当选中i为k值时，如果从i后面某个原本的前缀和要大于选k之后所得到的前缀和的话，说明k不是最优的
可以证明，假设选k为最优的，然后某个原本的前缀和为u,选k对应的前缀和为w，u>w,则在u这个位置如果选u的话，则后面的下限为u要大于k,因此k不是最优的，反之如果k是最优的，则保证了从k开始所有的u<=w
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,t;
void solve(){
cin>>n;
ll sum=0,k=0,ans=0;
ll mx=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
sum+=x;
mx=max(mx,sum);//单调递增
ans+=x;//选了对应k之后的值
if(ans<k) ans=k;
if(ans<mx){//如果原值大于对应k的值，说明下限还可以增大
ans=mx;
k=mx;
}
}
cout<<k<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
solve();
}
}标签：151,Rating,Educational,前缀,int,sum,ans,include,mx From： https://www.cnblogs.com/liyiyang/p/17536045.html