链接：https://ac.nowcoder.com/acm/contest/949/D
来源：牛客网
 

题目描述

水果店里有 nnn个水果排成一列。店长要求顾客只能买一段连续的水果。
小阳对每个水果都有一个喜爱程度 aia_iai​，最终的满意度为他买到的水果的喜欢程度之和。
如果和为正（不管是正多少，只要大于 000 即可），他就满意了。

小阳想知道在他满意的条件下最多能买多少个水果。

你能帮帮他吗？

输入描述:

第一行输入一个正整数 n，表示水果总数。第二行输入 n 个整数 aia_iai​，表示小阳对每个水果的喜爱程度。

输出描述:

一行一个整数表示结果。（如果 1 个水果都买不了，请输出 0）

示例1

输入

复制

5
0 0 -7 -6 1

输出

复制

1

备注:

1≤n≤2×106,∣ai∣≤1031 \leq n \leq 2 \times 10^6,|a_i| \leq 10^31≤n≤2×106,∣ai​∣≤103

---

思路：

前缀和排序，记录下标，那么必定后面的减去前面的是大于等于0的，

1、避免相减等于零，我们可以让id大的放到前面，就不会走max这一步

2、可能出现某一个前缀本身就是最长解，只需加上一个起始点，参与排序就行，减去起始点之后还是本身，

 

必须要满足左端点必须最小，右端点必须在左端点的右边，且尽量大

 

code：
 

#include<bits/stdc++.h>
using namespace std;const int inf = 0x3f3f3f3f;struct node
{int sum,id;bool operator < (const node &t) const{if(sum == t.sum ) return id > t.id; //避免两个0相减的情况return sum < t.sum;}
}a[2000010];int min_id = inf;
int ans = 0;int main()
{int n,x;cin>>n;for(int i = 1;i <= n; i++){cin >> x;a[i].sum = a[i-1].sum + x;a[i].id = i;}sort(a , a+n+1);//起始点参与排序 for(int i = 0; i <= n; i++){if(a[i].id < min_id)//更新当前最小id min_id = a[i].id;else  //更新答案 ans = max( ans , a[i].id - min_id );}cout<<ans;return 0;
}