的+已经为O整数连续的子数组的第k最大总和（nlogS）

本文介绍了的+已经为O整数连续的子数组的第k最大总和（nlogS）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在读这编辑和本声明糊涂了

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

如果数组元素都是非负，我们可以使用二进制搜索找到在O的答案（N日志S）时，其中S是一个子数组的最大总和。

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."

谁能解释上述表示的。

推荐答案

假设我们有一个数组之，这在指数第i 0的所有元素，以的总和存储第i ，因此，如果所有元素都是非负的，所以

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]

我们注意到，一个子阵列的总和（I，J）阵列 A 是总和[J] - 总和[我 - 1]

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

所以，对于一个数X，我们可以轻松地从子阵列如下的所有总和计算这个数字的排名：

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

最后，要找到哪个数字是第K 数量，我们可以使用的范围二进制搜索 0至S 并使用上述算法来计算排名，与S是一个子数组的最大总和。

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

所以，时间复杂度为O（nlogS log n）的。

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