AlgoMaster Logo

Max Value of Equation

points=[[1,3],[2,0],[5,10],[6,-10]],k=1
1public int findMaxValueOfEquation(int[][] points, int k) {
2    int maxValue = Integer.MIN_VALUE;
3    Deque<int[]> deque = new ArrayDeque<>();
4
5    for (int j = 0; j < points.length; j++) {
6        int xj = points[j][0];
7        int yj = points[j][1];
8
9        while (!deque.isEmpty() && xj - deque.peekFirst()[1] > k) {
10            deque.pollFirst();
11        }
12
13        if (!deque.isEmpty()) {
14            maxValue = Math.max(maxValue, yj + xj + deque.peekFirst()[0]);
15        }
16
17        while (!deque.isEmpty() && yj - xj >= deque.peekLast()[0]) {
18            deque.pollLast();
19        }
20
21        deque.offerLast(new int[]{yj - xj, xj});
22    }
23
24    return maxValue;
25}
0 / 20
points[1,3][2,0][5,10][6,-10]deque (value,x)maxValue: -∞