Блог пользователя prabhat7298

Автор prabhat7298, история, 5 лет назад, По-английски

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

One of the solution I found somewhere 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?

PS: I know it can be easily solved by binary searching on prefix subarray rather than on length but I want to know the correctnes of the solution or how it works

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If there is subarray of length l with sum > k, it doesn't guarantee that there exists subarray with length l-1. For example, if k=1 and array is [2, -1, 2], [2, -1, 2] is ok, but [2, -1] and [-1, 2] is not.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It can be done using some data structure (e.g. segment tree or Fenwick (binary indexed) tree). Let's precalc each prefix sum of the array — $$$pref_i$$$. Now sum on some segment $$$[l, r]$$$ is equal to $$$pref_r - pref_{l - 1}$$$ ($$$pref_{-1} = 0$$$). $$$pref_r - pref_{l - 1} > k$$$ then $$$pref_r - k > pref_{l - 1}$$$. Now let's iterate over each element we should minimum $$$val$$$ on segment $$$(-\infty, pref_i - k)$$$ and update $$$val_{pref_i}$$$ with $$$i$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you very much! But could you plz also comment on the correctness of the above solution?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, for each $$$r$$$ we choose only subarrays with $$$sum > k$$$ because of the equation and choose the minimum $$$l - 1$$$ so that $$$r - l + 1$$$ is maximal. If you don't understand it now you should try solving easier tasks.