hi_cf's blog

Find all maximum sub-array in which all pairs have their sum >= k
By hi_cf, 10 years ago, In English

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

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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]
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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] .

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          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)

          → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Because it's not maximum subarray (their length is too small).

    → Reply