Maximum Sum and Distance | Algorithms Notes
Given an array A of n integers, design a linear time algorithm to find i and j such that A[i] + A[j] + (i – j) is maximized subject to i > j.
Solution:
The optimal solution ending at i is to pair with j such that A[j] – j is maximized over all j < i. Thus we can scan the array from beginning and remember the current maximum of A[j] – j in all previous locations. Then, we can find optimal solution easily.
Read full article from Maximum Sum and Distance | Algorithms Notes
No comments:
Post a Comment