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

Finding Maximum Sum Pair which are atleast K distance apart
Автор hulk_baba, история, 8 лет назад, По-английски

Hello all. I was solving one problem which boils down to finding 2 numbers (precisely their indices) in an array which are at least some distance k apart such that their sum is maximum. How can i solve this problem in O(n).

eg indice 1 2 3 4 5 6 7 8 9 10 arr[i] 4 18 18 20 11 17 17 14 14 17

given k = 3; answer is : 4(20) , 7(17).

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

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

What you can do is have an array that stores the maximum value seen so far in arr and a second array that stores the index of that maximum value. So for the given example the arrays would look like:

Max: {4, 18, 18, 20, 20, 20, 20, 20, 20, 20}

Index: {0, 1, 1, 3, 3, 3, 3, 3, 3, 3}

And then for every element in the array greater than or equal to k (0-based indexing), if arr[i] + max[i-k] is greater than the current max, store the indices i and index[i-k] as your current answer.

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

    Thank you, Ahmad. I kind of get you but still not very convinced why this works?

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

      Since the array keeps track of the largest element so far at some position x, for every number in the array you can figure out what partner would be optimal for it by looking at the index array (since that stores the index of the largest seen value) at postition i-k (it needs to be at least k away from i). So with that you can find the optimal partners for each number and then take the maximum pairing.

      → Ответить