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&lt;=N;i++){
        for(k=1;k&lt;=N-i+1;k++){
            for(j=0;j&lt;i;j++){
                sum += arr[j+k-1];
            }
            if(sum&lt;0)
                count++;
            sum = 0;
        }
    }
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]$