LeetCode1425. Constrained Subsequence Sum -DP : NileshBlog.Tech

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. ‘

Table of Contents

Approach: Dynamic Programming with a Heap

Initialize a dynamic programming (DP) array dp of size n to store the maximum constrained sum ending at index i.
Create a deque (priority queue (MaxHeap)) named MaxHeapto maintain a decreasing order of maximum elements.

Initialize maxSum to the first element of the input array, as the initial maximum sum.
Initialize dp[0] with the first element of the input array.
Push a tuple (dp[0], 0) into MaxHeap, representing the maximum sum ending at index 0.

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.

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:

i	Current Element (`nums[i]`)	`dp[i]` Calculation	Updated `maxSum`	Updated `maxHeap`
0	10	`dp[0] = max(10, 10) = 10`	10	[(10, 0)]
1	2	`dp[1] = max(2, 2 + 10) = 12`	12	[(10, 0), (12, 1)]
2	-10	`dp[2] = max(-10, -10 + 12) = 2`	12	[(10, 0), (12, 1)]
3	5	`dp[3] = max(5, 5 + 12) = 17`	17	[(12, 1), (17, 3)]
4	20	`dp[4] = max(20, 20 + 17) = 37`	37	[(17, 3), (37, 4)]

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[0];
        dp[0] = nums[0];
        maxHeap.push({dp[0], 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[0];
        dp[0] = nums[0];
        maxHeap.add(new Pair<>(dp[0], 0));
        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]);
            maxHeap.add(new Pair<>(dp[i], 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 = [0] * n
        MaxHeap= collections.deque()
        maxSum = nums[0]
        dp[0] = nums[0]
        MaxHeap.append((dp[0], 0))
        for i in range(1, n):
            while MaxHeap and MaxHeap[0][1] < i - k:
                MaxHeap.popleft()
            dp[i] = max(nums[i], nums[i] + MaxHeap[0][0])
            maxSum = max(maxSum, dp[i])
            while MaxHeapand dp[i] >= MaxHeap[-1][0]:
                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[0];
        dp[0] = nums[0];
        MaxHeap.push([dp[0], 0]);
        for (let i = 1; i < n; i++) {
            while (MaxHeap.length > 0 && MaxHeap[0][1] < i - k) {
                MaxHeap.shift();
            }
            dp[i] = Math.max(nums[i], nums[i] + MaxHeap[0][0]);
            maxSum = Math.max(maxSum, dp[i]);
            while (MaxHeap.length > 0 && dp[i] >= MaxHeap[MaxHeap.length - 1][0]) {
                MaxHeap.pop();
            }
            MaxHeap.push([dp[i], i]);
        }
        return maxSum;
    
};

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