Kth maximum sum of a contiguous subarray of +ve integers in O(nlogS)

Question

I was reading this editorial and got confused with this statement:

If the array elements are all non-negative, we can use binary search to find the answer in O(n log S) time, where S is the maximum sum of a subarray."

Can anyone explain the above statement.

Answer 1

Assume that we have an array sum, which at index ith store the sum of all element from 0 to ith, so, if all element are non-negative, so

 sum[0] <= sum[1] <= sum[2] ... <= sum[i] ... <= sum[n - 1]

We notice that, the sum of a sub array (i, j) of array A is sum[j] - sum[i - 1]

So, Given a number X, we can easily calculate the rank of this number from all sum of sub array of A as follow:

int rank = 0;
for(int i = 0; i < n; i++){
    int index = minimum index which sum[i] - sum[index] >= X;
    //As sum[0] <= sum[1] <=... , we can use binary search to find index
    rank += index;
}

Finally, to find which number is the Kth number, we can use binary search in range O to S and use the above algorithm to calculate the rank, with S is the maximum sum of a subarray.

int start = 0;
int end = S;
while(start <= end){
   int mid = (start + end) >> 1;
   int rank = calRank(mid , sum)
   if(rank < mid)
      end = mid - 1;
   else if(rank > mid)
      start = mid + 1;
   else
      break;
}

So, time complexity is O(nlogS log n).