易于发现的是，假设设置的保护分为k，且k是为了避免某一项负值ai。令s=sum(a0, ai-1)，则将k设置为s一定更优于介于[s-ai,s)中的任何值。
那么就需要研究什么情况下，我们选择当前的前缀和作为k，以使得最终值最大。应该是为了避免最小的一段递减。
因而可以研究最小子数列，类kadane解法。最小子数列前的前缀和就是解。
#include<iostream> #include<algorithm> #include<vector> #include<string> #include<map> #define ll long long #define pii pair<int, int> using namespace std; const int N = 3E5 + 10; const ll INF = INT64_MAX; int n; ll a[N], s[N], k; int main(){ ios::sync_with_stdio(0);cin.tie(0),cout.tie(0); int cas; cin >> cas; while(cas--) { cin >> n; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; }// 找出递减最多的子序列 ll sum = 0, ans = INF, tar = -1; for(int i = 1 ; i <= n ; i++) { s[i] = min(s[i - 1] + a[i], a[i]); if(s[i] < ans) { tar = i; ans = s[i]; } } if(ans >= 0) { cout << 0 << endl; }else { ll tmp = 0, tt = tar; while(tmp != ans) { tmp += a[tt]; tt--; } tmp = 0; for(int i = 1 ; i <= tt ; i++) { tmp += a[i]; } cout << tmp << endl; } } return 0; }