Maximum length subarray having sum greater than K

Question

We want to find largest length subarray having sum greater than k.

One of the solution that works is binary searching on the length of subarray. Length of subarray can vary from 1 to n. We can binary search in range low=1 to high=n and for every mid=(low+high)/2 we can check for all subarray of length=mid if any subarray has sum greater than k in O(n). If any such subarray exist then we can search for higher length subarray i.e. low=mid+1 otherwise we decrease the search length i.e. 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;
}

What puzzles me is that if we get sum < k for present length subarray then increasing the search length of subarray will ensure that we'll get some subarray having subarray>k. And if we have subarray>k for any length then by decreasing search length we can get more such subarrays having greater than k sum. It could be that we could have decreased search length to get some subarray>k. So, the question boils down to deciding the predicate of binary search i.e. at each step how we'll decide to change the search range?

Answer 1

The algorithm is incorrect (apart from bugs in the implementation).

Consider the array [6 -7 3 0 0 0 3] with k=5.

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

But the true answer is [3 0 0 0 3] with length 5.