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

i reading this editorial , got confused statement:

if array elements non-negative, can use binary search find answer in o(n log s) time, s maximum sum of subarray."

can explain above statement.

assume have array sum, @ index ith store sum of element 0 ith, so, if element non-negative,

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

we notice that, sum of sub array (i, j) of array a sum[j] - sum[i - 1]

so, given number x, can calculate rank of number sum of sub array of follow:

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

finally, find number kth number, can use binary search in range o s , use above algorithm calculate rank, s maximum sum of 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 o(nlogs log n).