# Print the number of subarrays of an array having negative sums

Problem statement: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $[1,-2, 4, -5, 1]$ there are 9 subarrays whose sum is negative. Subarray means sequential array within an array.

My code: It's complexity is $\theta(n^{2})$ as we can see. I have applied brute force technique. How can I improve my code/pseudocode?

    int sum=0,count=0;
for(int i=1,k,j;i<=N;i++){
for(k=1;k<=N-i+1;k++){
for(j=0;j<i;j++){
sum += arr[j+k-1];
}
if(sum<0)
count++;
sum = 0;
}
}

• Looks like $\Theta(n^3)$ to me. – gnasher729 Jul 20 '17 at 22:35
• sum should be set to zero just before the "for (j = ..." loop and nowhere else. Try to prove the correctness of your code which requires that sum must be zero just at that point - much easier if that is the point where you set it. – gnasher729 Jul 20 '17 at 22:41
• @gnasher729 This code has been successfully passed all the test cases on a competitive platform. We have to set sum = 0 always as to ensure previous summation doesn't reflect in newer summation. And this code checking all $\frac{n*(n+1)}{2}$ sub arrays individually so $\theta(n^{2})$ . – Mr. Sigma. Jul 21 '17 at 5:15
• " This code has been successfully passed all the test cases on a competitive platform." -- That doesn't tell us anything about $\Theta$-s. – Raphael Jul 22 '17 at 10:00
• And who told you the testcase statement was a reason of complexity question? @Raphael It was to answer code is correct. – Mr. Sigma. Jul 22 '17 at 11:27

An $O(n \log n)$ solution:
Find prefix sums $S[i] = \sum_{k=0}^{i} a[k]$
Set $S[-1] = 0$
Now count the number of inversion pairs in $S[-1], S[0], \dots, S[n-1]$
• @Fire: $S[j+k], S[j]$ is an inversion pair implies $S[j+k] - S[j] < 0$ and so $a[j+1] + \dots + a[j+k] \lt 0$. The $S[-1]$ helps with sub-arrays starting at $a[0]$. – Aryabhata Jul 22 '17 at 16:32