Count Non-Negative Subarrays
EasyPractice library · +10 XPsliding windowprefix sumsarrays
Given an array of N integers, count the number of contiguous subarrays whose sum is non-negative (greater than or equal to zero).
Input
The first line contains an integer N. The second line contains N space-separated integers representing the array elements.
Output
Print a single integer: the count of non-negative sum subarrays.
Constraints
1 <= N <= 1000. Each array element is between -1000 and 1000.
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 -2 3 4 -5
Output
11
Subarrays: [1], [1, -2, 3], [1, -2, 3, 4], [-2, 3], [-2, 3, 4], [3], [3, 4], [4]. Their sums are 1, 2, 6, 1, 5, 3, 7, 4 respectively. All are non-negative. Count is 8.
Example 2
Input
3 -1 -2 -3
Output
0
No subarray has a non-negative sum. Count is 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 -2 3 4 -5
Example 2 input
3 -1 -2 -3