Create Constrained Subsequence Sum.java

varunu28 · web-flow · commit 42b485199d6a · 2023-10-21T07:53:53.000-07:00
diff --git a/Hard/Constrained Subsequence Sum.java b/Hard/Constrained Subsequence Sum.java
@@ -0,0 +1,16 @@
+class Solution {
+    public int constrainedSubsetSum(int[] nums, int k) {
+        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
+        pq.add(new int[]{nums[0], 0});
+        int result = nums[0];
+        for (int i = 1; i < nums.length; i++) {
+            while (i - pq.peek()[1] > k) {
+                pq.remove();
+            }
+            int curr = Math.max(0, pq.peek()[0]) + nums[i];
+            result = Math.max(result, curr);
+            pq.add(new int[]{curr, i});
+        }
+        return result;
+    }
+}
