Description
Given an array points representing points on X-Y plane sorted by x-values, find maximum value of yi + yj + |xi - xj| where |xi - xj| <= k.
Examples
Input:
points = [[1,3],[2,0],[5,10],[6,-10]], k = 1Output:
4Explanation:
Max at points [1,3] and [2,0].
Input:
points = [[1]], k = 1Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
points = [[0,1],[1,3],[4,4],[5,2]], k = 3Output:
8Explanation:
Valid pairs require |xi - xj| <= 3. Pair (1,3)&(4,4): yi+yj+|xi-xj| = 3+4+3 = 10, and |1-4|=3 <= 3, so this is valid. The maximum value of yi+yj+|xi-xj| among all valid pairs is 10.
Constraints
- •
2 ≤ points.length ≤ 10^5 - •
-10^8 ≤ xi, yi ≤ 10^8