Tag Archives: ad-hoc

Nonnegative Partial Sums

Problem Statement

Solution:

  1. compute partial sums array S of A (original array), i.e. S[i]=S[i-1]+A[i-1]. (O(n))
  2. compute B[i]=min{ S[j] : j<i} for each i<n. (O(n))
  3. compute C[i]=min{ S[j] : j>=i} for each i<n. (O(n))
  4. execute the loop below. (O(n))
int res = 0;
for(int i=0; i&lt;n; i++)
  if(C[i]-S[i] &lt;= 0 &amp;&amp; B[i]+(S[n]-S[i]) &lt;= 0)
    res++;
return res;
Advertisements