# LeetCode1425. Constrained Subsequence Sum (Medium) – DP + Heap Appraoch

LeetCode 1425. Constrained Subsequence Sum :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Constrained Subsequence Sum” or “LeetCode 1425. ‘

## Approach: Dynamic Programming with a Heap

1. Initialize a dynamic programming (DP) array `dp` of size `n` to store the maximum constrained sum ending at index `i`.
2. Create a deque (priority queue (MaxHeap)) named MaxHeapto maintain a decreasing order of maximum elements.
3. Initialize `maxSum` to the first element of the input array, as the initial maximum sum.
4. Initialize `dp` with the first element of the input array.
5. Push a tuple `(dp, 0)` into `MaxHeap`, representing the maximum sum ending at index 0.
6. Loop from index 1 to `n-1`:
• Remove elements from the front of MaxHeapif they are out of the constraint range (i.e., index is more than `k` positions away).
• Calculate the constrained sum `dp[i]` at index `i` as the maximum of the current element `nums[i]` and the maximum element in MaxHeapplus `nums[i]`.
• Update `maxSum` if `dp[i]` is greater than the current `maxSum`.
• Remove elements from the back of MaxHeapas long as they are less than or equal to `dp[i]`.
• Push a tuple `(dp[i], i)` into `MaxHeap`.
7. The `maxSum` holds the maximum constrained subsequence sum.

table representing the step-by-step calculation of the example with the input array `nums = [10, 2, -10, 5, 20]` and `k = 2`:

• Index (i): The current index being processed.
• Current Element (nums[i]): The value of the element at index i.
• `MaxHeap`: The contents of the MaxHeap after processing index i.
• `dp[i]`: The maximum constrained sum ending at index i.
• `maxSum`: The maximum constrained subsequence sum found up to index i.

## Codes for Appraoch DP + MaxHeap

### C++: Dynamic Programming with a Heap

``````class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> dp(n);
priority_queue<pair<int, int>> maxHeap;
int maxSum = nums;
dp = nums;
maxHeap.push({dp, 0});
for (int i = 1; i < n; i++) {
while (maxHeap.top().second < i - k) {
maxHeap.pop();
}
dp[i] = max(nums[i], nums[i] + maxHeap.top().first);
maxSum = max(maxSum, dp[i]);
maxHeap.push({dp[i], i});
}
return maxSum;
}
};``````

### Java: LeetCode 1425

``````import java.util.*;

class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
PriorityQueue<Pair<Integer, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getKey() - a.getKey());
int maxSum = nums;
dp = nums;
for (int i = 1; i < n; i++) {
while (maxHeap.peek().getValue() < i - k) {
maxHeap.poll();
}
dp[i] = Math.max(nums[i], nums[i] + maxHeap.peek().getKey());
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
}``````

### Python: Leetcode 1425 Dynamic Programming with a Heap/Priority Queue

``````import collections

class Solution:
def constrainedSubsetSum(self, nums, k):
n = len(nums)
dp =  * n
MaxHeap= collections.deque()
maxSum = nums
dp = nums
MaxHeap.append((dp, 0))
for i in range(1, n):
while MaxHeap and MaxHeap < i - k:
MaxHeap.popleft()
dp[i] = max(nums[i], nums[i] + MaxHeap)
maxSum = max(maxSum, dp[i])
while MaxHeapand dp[i] >= MaxHeap[-1]:
MaxHeap.pop()
MaxHeap.append((dp[i], i))
return maxSum
``````

### JavaScript: Constrained Subsequence Sum Solution

``````/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var constrainedSubsetSum = function(nums, k) {

const n = nums.length;
const dp = new Array(n).fill(0);
const MaxHeap= [];
let maxSum = nums;
dp = nums;
MaxHeap.push([dp, 0]);
for (let i = 1; i < n; i++) {
while (MaxHeap.length > 0 && MaxHeap < i - k) {
MaxHeap.shift();
}
dp[i] = Math.max(nums[i], nums[i] + MaxHeap);
maxSum = Math.max(maxSum, dp[i]);
while (MaxHeap.length > 0 && dp[i] >= MaxHeap[MaxHeap.length - 1]) {
MaxHeap.pop();
}
MaxHeap.push([dp[i], i]);
}
return maxSum;

};``````
##### List of Some important Leet code Questions: I am Nilesh,3+ years Exp of SEO, content writing, and keyword research. Also rocks it as a software dev with skills in OS, web dev, Flask, Python, C++, data structures, and algorithms. 3 on Leetcode, 5*on Hackerrank more platform.