Maximum Sum and Distance

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.

Reference: Stackoverflow