Given N points on an axis x1, x2, x3, …, xN where (0 < x1 < x2 < … < xN).
Each point i has a value p_i.

(1) Find a pair (i, j) that maximize p_i + p_j + |x_i - x_j|.

Example:
Points: [0, 3, 6]
Values: [-5, 4, 7]
Return: Either the point pair of (3, 6) or (6, 6)
Reasoning is that for these two points, p_i + p_j + |x_i - x_j| = 14

Full evaluation of the example above with (Point pairs) -> result

0, 0 -> (-5 + -5) + (0 - 0)= -10
0, 3 -> (-5 + 4) + (3 - 0) = 2
0, 6 -> (-5 + 7) + (6 - 0) = 4
3, 3 -> (4 + 4) + (3 - 3) = 8
3, 6 -> (4 + 7) + (6 - 3) = 14
6, 6 -> (7 + 7) + (6 - 6) = 14

Followup hint I was given: keep |x_i - x_j| <= M. Didn't help me at all...

I couldn't get beyond an optimized O(n^2) approach.

Looks like @moli2398 was able to solve it with dp below.

Leetcode question: https://leetcode.com/problems/max-value-of-equation/