Divide the Sequence
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 649 Accepted Submission(s): 331
Problem Description
Alice has a sequence A, She wants to split A into as much as possible continuous subsequences, satisfying that for each subsequence, every its prefix sum is not small than 0.
Input
The input consists of multiple test cases.
Each test case begin with an integer n in a single line.
The next line contains n integers A1,A2⋯An.
1≤n≤1e6
−10000≤A[i]≤10000
You can assume that there is at least one solution.
Each test case begin with an integer n in a single line.
The next line contains n integers A1,A2⋯An.
1≤n≤1e6
−10000≤A[i]≤10000
You can assume that there is at least one solution.
Output
For each test case, output an integer indicates the maximum number of sequence division.
Sample Input
6
1 2 3 4 5 6
4
1 2 -3 0
5
0 0 0 0 0
Sample Output
6
2
5
Author
ZSTU
Source
解析：要使所有前缀和不小于0，只需从后向前扫描整个序列a[]，如果a[i]非负，则a[i]是一个满足条件的子序列；否则，继续向前扫描，直到前缀和非负，形成一个满足条件的子序列。如此进行贪心即可。
#include <cstdio>
#define ll long long
const int MAXN = 1e6+5;
int a[MAXN];
int main()
{
int n;
while(~scanf("%d", &n)){
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
ll sum = 0;
int ans = 0;
for(int i = n-1; i >= 0; --i){
sum += a[i];
if(sum >= 0){
++ans;
sum = 0;
}
}
printf("%d
", ans);
}
return 0;
}