Clever Geek Handbook

Counting the number of contiguous subarrays with positive sum in O (nlogn) using O (n) transform

I'm interested in finding the number of contiguous subarrays that add up to a positive value (sum> 0).

More formally, given an array of integers A [1, ..., n] I'm looking to count pairs of integers (i, j) such that 1 <= i <= j <= n and A [i] +. .. + A [J]> 0.

I am familiar with Kadane's algorithm for finding the maximum sum of a subamma in O (n), and using a similar approach, I can count the number of these subarrays in O (n ^ 2).

For this, I take the cumulative sum T (i). Then I calculate T (j) -T (i-1) for all j = 1, ..., n and i = 1, ..., j and just write down the differences, which are positive.

Apparently, although there is an O (n) time procedure that turns this problem into a task of counting the number of inversions (which can be achieved in O (nlogn) using say merge-sort). Try it though I can, though, I haven't been able to find this conversion.

I do realize that somehow I have to match this inversion to the fact that the sum of the elements between the pair (i, j) is positive.

Does anyone have any directions on how to do this? Any help is appreciated.

EDIT: I am actually looking for an O (n) -transform, not an alternative (non-transform-based and counting inversion) solution for finding the number of submatrices.

+3


source to share


1 answer


Using the original array A, create another array sumA so that:

sumA[i] = A[0] + A[1] + ... + A[i].

Now in this array sumA [], if there are two indices i, j (i <j), such that sumA [i] SuMa [J],



Then sumA[j] - sumA[i] > 0

. This is just the sum of all the elements between the indices i and j.

Hence, the problem is reduced to finding the number of inversions for the inverse of this array. This can be accomplished by sorting the sumA [] array in descending order using mergesort and calculating the number of inversions encountered in the process.

+4


source






More articles:


All Articles