总和大于 K 的最大长度子数组

Question

我们想找到总和大于k的最大长度子数组。

一种可行的解决方案是对子数组的长度进行二进制搜索。子数组的长度可以从 1 到 n 不等。我们可以在 low=1 到 high=n 的范围内进行二进制搜索，并且对于每个 mid=(low+high)/2 我们可以检查所有 length=mid 的子数组，如果任何子数组的总和大于 O(n) 中的 k。如果存在任何这样的子数组，那么我们可以搜索更高长度的子数组，即 low=mid+1 否则我们减少搜索长度，即 high=mid-1.

int maxlen(vector<int> v)
{
    int hi = n, lo = 1, ans = -1, mid, cnt = 0;
    while(lo <= hi) {
        mid = hi+lo>>1;
        if(cnt = count(mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
     return ans;
 }

int count(int len) {
    int cnt = 0;
    for(int i = len; i <= n; i++)
        if(prefixsum[i] - prefixsum[i - len] > K)
            cnt++;
    return cnt;
}

令我困惑的是，如果我们得到当前长度子数组的总和 < k，那么增加子数组的搜索长度将确保我们将得到一些子数组 > k 的子数组。如果我们有任何长度的子数组 > k，那么通过减少搜索长度，我们可以获得更多这样的子数组，其总和大于 k。可能是我们可以减少搜索长度以获得某个>k 的子数组。所以，问题归结为决定二分查找的谓词，即在每一步我们将如何决定改变搜索范围？

Answer 1

算法不正确（除了实现中的错误）。

考虑 k=5 的数组 [6 -7 3 0 0 0 3]。

low=1 high=7 mid=4  no subarray > k
low=1 high=3 mid=2  no subarray > k
low=1 high=1 mid=1  subarray [6] has sum > k
result: [6] with length 1

但真正的答案是 [3 0 0 0 3]，长度为 5。

总和大于 K 的最大长度子数组

Maximum length subarray having sum greater than K

c++

sub-array

c++14