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

How to solve this problem?
Автор rahul_bhaiya_sabka_baap, история, 6 лет назад, По-английски

Given an array of N numbers and a number K find the maximum subarray size such that the average of the elements of the subarray >= k

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

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

Create a new array B, such that B[i] = A[i] — K. Then each subarray with sum  ≥ 0 in B will have average  ≥ K in A. Now we can simply solve the problem of finding the longest array with non-negative sum (any BST and even std::map is enough for it).

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

    Thanks @radoslav11. I got your point of auxilliary array B. But can you please tell how to find longest subarray with non-negative sum using map?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I'm stupid.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +25 Проголосовать: не нравится

        Longest subarray of non-negative integers != longest subarray with non-negative sum.

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

          lol I thought I linked something else. Sry about that.

          Basically the idea with map is to create partial sums on B. Let that array be pB. Then we are interested in subarrays such that pB[L] <= pB[R]. Well then we simply go from 1st to last element and add pB[i] to our set/map if there is no element in the map which is better than the current one. By better I mean such position X, that pB[X] <= pX[i] and X < i. After adding the current i to the map, we do one upper bound query — we want the largest sum <= pX[i] (because we are also keeping the left indexes in increasing order).

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

            The problem is also solvable in linear time:

            Do the prefix sum, as you said, and we'll also add the element 0 to the beginning of the array. now we're interested in the longest subarray [L, R] such that Bl ≤ Br. Additionally we'll create another array P, which will be the prefix minimum of array B: Pi = minj ≤ iBj.

            We will iterate on array B from end to beginning, while finding all candidate indicies to be R, and for each we find the leftmost L. Notice that an index is a candidate to be right end of the optimal subarray if it is larger than all the elements we've found so far in the current suffix. Then for each such element we want to find the leftmost L such that Pl ≤ Br. Since the array P is non-increasing and our candidates are increasing, we can find the L for each R in total linear time with a 2 pointer approach.

            → Ответить