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;        }    }
Print the number of subarrays of an array having negative sums
algorithms;searching
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]$