O(nlogS) 中 +ve 个整数的连续子数组的第 K 个最大和

Question

我正在阅读这篇社论，并对以下声明感到困惑：

如果数组元素都是非负数，我们可以使用二分查找在 O(n log S) 时间内找到答案，其中 S 是子数组的最大和。”

谁能解释一下上面的说法。

Answer 1

假设我们有一个数组sum，它在索引处ith存储从 0 到 的所有元素的总和ith，所以，如果所有元素都是非负的，那么

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

我们注意到，数组(i, j)的一个子数组的和A是sum[j] - sum[i - 1]

所以，给定一个数 X，我们可以很容易地从 A 的子数组的所有和中计算这个数的秩，如下所示：

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;
}

最后，要找出哪个数是Kth数，我们可以在范围内使用二分查找，O to S并使用上述算法计算秩，其中S是一个子数组的最大和。

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;
}

所以，时间复杂度是 O(nlogS log n)。