Constrained Subsequence Sum LeetCode solution in Java

1
class Solution {
2
  public int constrainedSubsetSum(int[] nums, int k) {
3
    int n = nums.length;
4
    int[] dp = new int[n];
5
    int res = nums[0];
6
    Queue<Integer> queue = new PriorityQueue<>((a, b) -> dp[b] - dp[a]); // Declaring Max heap
7

8
    Arrays.fill(dp, Integer.MIN_VALUE);
9
    dp[0] = nums[0];
10
    queue.offer(0);
11

12
    for (int j = 1; j < n; j++) {
13
      int i = Math.max(j - k, 0); // get the furthest index possible
14
      while (!queue.isEmpty() && queue.peek() < i)
15
        queue.poll(); // find the global max in the specified range for that particular j index
16
      int idx = queue.peek();
17
      dp[j] = Math.max(dp[idx] + nums[j], nums[j]);
18
      res = Math.max(res, dp[j]);
19
      queue.offer(j);
20
    }
21
    return res;
22
  }
23
}