一、思路：

根据题意，k一定是前缀和的其中一个数。假设存在一个数i，使得pre【i】加上 i+1到n中的数（经k处理后）使得最终结果maxv最大。

pre【i】很容易求出。

i+1到n后面的处理：实际上是找出两段区间，使得【i+1，j】的区间和为负，【j+1，n】的区间和为正。因为从i之后如果sum小于pre【i】就加上0.那么这个区间肯定是最大的一个负区间。又因为每一个i+1到n，都会到达n，实际上可以从n向前处理，用一个后缀和的思想。记suf【i】 为n 到 i 的最小正区间（从n开始，连续）的区间和。用一个动态规划的思想。如果a【i】 < 0，suf【i】 = suf【i+1】；如果a【i】>=0，suf【i】等于 max（从n到i的后缀和，suf【i+1】）（因为如果后缀和大于suf【i+1】，那么中间这段区间肯定是非负的。那么suf【i】 = 后缀和） 因此suf【i】=max（后缀和，suf【i+1】）。

二、代码：

#include 
#include
#include
#include
using namespace std;const int N = 3e5 + 10;typedef long long ll;ll a[N];ll pre[N];ll suf[N];void solve()
{ll n;cin >> n;memset(pre, 0, sizeof pre);memset(suf, 0, sizeof suf);for (int i = 1; i <= n; i++) {cin >> a[i];pre[i] = pre[i - 1] + a[i];}ll t = 0;for (int i = n; ~i; i--) {t += a[i];suf[i] = max(suf[i + 1], t);}ll maxv = 0;ll res = 0;for (int i = 0; i <= n; i++) {if (pre[i] + suf[i + 1] > maxv) {maxv = pre[i] + suf[i + 1];res = pre[i];}}cout << res << endl;
}
int main() 
{int t;cin >> t;while (t--) {solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！