Max Value of Equation
Given an array of points sorted by x-coordinate and an integer k, find the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and i < j.

30:00

Max Value of Equation
hard
Topics
Companies

Given an array of points sorted by x-coordinate and an integer k, find the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and i < j.

Example 1:
Input: {"points":[[1,3],[2,0],[5,10],[6,-10]],"k":1}
Output: 4
Constraints:

  • 3≤points.length≤1053 \leq \text{points.length} \leq 10^5

  • points[i].length==2\text{points}[i].\text{length} == 2

  • −108≤xi,yi≤108-10^8 \leq x_i, y_i \leq 10^8

  • points is sorted by xix_i in strictly increasing order.

  • 0<k≤2×1080 < k \leq 2 \times 10^8

Input
arr ={"points":[[1,3],[2,0],[5,10],[6,-10]],"k":1}

Points: [[1,3], [2,0], [5,10], [6,-10]], k=1

Points on Coordinate Plane (k=1)

(1,3)(2,0)(5,10)(6,-10)

Monotonic Deque (yi - xi, xi)

empty

Max Value:

-∞

Variables
No variables to display
DepthFunction Call
Stack empty
0/5