hulk_baba's blog

Finding Maximum Sum Pair which are atleast K distance apart
By hulk_baba, history, 8 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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.

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

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

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

      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.

      → Reply