Solution:

- compute partial sums array S of A (original array), i.e. S[i]=S[i-1]+A[i-1]. ()
- compute B[i]=min{ S[j] : j<i} for each i<n. ()
- compute C[i]=min{ S[j] : j>=i} for each i<n. ()
- execute the loop below. ()

int res = 0; for(int i=0; i<n; i++) if(C[i]-S[i] <= 0 && B[i]+(S[n]-S[i]) <= 0) res++; return res;

Advertisements