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

Find all maximum sub-array in which all pairs have their sum >= k
Автор hi_cf, 9 лет назад, По-английски

Find all maximum sub-array in which all pairs have their sum >= k. I feel it can be solved using monotonic queue like this solution , but i am not able to think correct answer. Please give some hints.

e.g. Array :[ 1 5 2 3 6 5 4 2 2 8 ] and K = 8

then answer is [ 3 6 5 ] or [6 5 4 ] because any pair's sum is greater than or equal to 8

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

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

Yes, it can be solved using monotonic queue and two pointers.

Sub-array [l..r] is "good", if minimum(l..r) + second minimum(l..r) >= k, and that information can be stored in monotonic queue.

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

    I tried . code but it does work for all cases . What am i doing wrong ?

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

      1) You use stack with minimum, but you need queue with minimum. Queue implements on two stack :

      • queue.add — push at first stack,
      • queue.poll — pop from second stack; if second stack is empty, you push all elements from first stack to second.

      2) You check minimum on segment + current > k, but it is not correct. You need check minimum on segment + next after minimum (second minimum) on segment > k.

      For example,

      Array :[ 1 5 2 3 6 5 4 2 2 8 ] and K = 8

      • Index = 1 -> queue = [1]
      • Index = 2 -> queue = [1, 5] -> min = 1, second min = 5, 1 + 5 = 6 < 8, so we poll 1 from queue
      • Index = 3 -> queue = [5, 2] -> min = 2, second min = 5, 2 + 5 = 7 < 8, so we poll 5 from queue
      • Index = 4 -> queue = [2, 3] -> min = 2, second min = 3, 2 + 3 = 5 < 8, so we poll 2 from queue
      • Index = 5 -> queue = [3, 6] -> min = 3, second min = 6, 3 + 6 = 9 >= 8, so we have correct sub-array [3, 6]
      • Index = 6 -> queue = [3, 6, 5] -> min = 3, second min = 5, 3 + 5 = 8 >= 8, so we have correct sub-array [3, 6, 5]
      • Index = 7 ->
      • queue = [3, 6, 5, 4] -> min = 3, second min = 4, 3 + 4 = 7 < 8, so we poll 3 from queue
      • queue = [6, 5, 4] -> min = 4, second min = 5, 4 + 5 = 9 >= 8, so we have correct sub-array [6, 5, 4]
      • Index = 8 -> queue = [6, 5, 4, 2] -> 2 + 4 = 6 < 8 -> we poll 6, 5, 4
      • Index = 9 -> queue = [2, 2] -> 2 + 2 = 4 < 8 -> we poll 2
      • Index = 10 -> queue = [2, 8] -> 2 + 8 = 10 >= 8 -> we have correct sub-array [2, 8]
      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Since queue in your solution is not monotonic ( increasing or decreasing ). How would you determine minimum and second minimum in O(1) ?

        for e.g. at index 7 , queue = [3, 6, 5, 4] .

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

          I use queue based on two stacks for minimum.

          You can store at stack not only element, but triple(element, current minimum at stack, current second minimum at stack).

          Queue for minimum is two stacks. When we add element in queue, we push triple in first stack. When we poll element, we pop triple from second stack; if second stack is empty, we push all triples from first stack in second in reverse order:

          while (!first.empty()) second.push(first.pop());

          Minimum and second minimum in queue is minimum and second minimum of next 4 values:

          • first.minimum,
          • first.secondmin,
          • second.min,
          • second.secondmin.

          For more information you can read this article (sorry, it is in Russian)

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

I am sorry, but why is [ 2 8 ] or [ 8 ] not included in the answer ?

→ Ответить