Finding Maximum Sum Pair which are atleast K distance apart

Revision en1, by hulk_baba, 2016-12-29 02:14:01

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hulk_baba 2016-12-29 02:14:01 440 Initial revision (published)