1425. Constrained Subsequence Sum Solution

The problem

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approach overview

Problem Overview: Given an integer array nums and an integer k, choose a subsequence such that the difference between consecutive chosen indices is at most k. The goal is to maximize the subsequence sum.

Approach 1: Dynamic Programming (Brute Window Scan) (Time: O(nk), Space: O(n))

Define dp[i] as the maximum subsequence sum that ends at index i. To compute it, look at the previous k positions and extend the best subsequence: dp[i] = nums[i] + max(0, dp[i-k...i-1]). This requires scanning up to k elements for every index. The approach demonstrates the core dynamic programming transition but becomes slow when k is large because every step performs a window maximum search.

Approach 2: Dynamic Programming with Priority Queue (Heap) (Time: O(n log k), Space: O(n))

Replace the repeated window scan with a max heap storing pairs (dp value, index). While iterating through the array, remove heap entries whose index is more than k behind the current position. The heap top always gives the largest valid dp value within the window. Compute dp[i] = nums[i] + max(0, top), then push the new state back into the heap. This reduces the lookup cost to log k while maintaining the sliding window constraint.

Approach 3: Dynamic Programming with Sliding Window Maximum (Monotonic Deque) (Time: O(n), Space: O(n))

The optimal approach maintains the window maximum using a monotonic deque. Store indices of dp values in decreasing order so the front always holds the maximum candidate. Before processing index i, remove indices outside the k window. Compute dp[i] = nums[i] + max(0, dp[deque front]). After computing dp[i], remove smaller values from the back of the deque to preserve decreasing order and push i. Each index enters and leaves the deque once, producing linear time. This technique combines dynamic programming with a sliding window maximum implemented using a monotonic queue.

Recommended for interviews: Interviewers typically expect the monotonic deque solution with O(n) time. Explaining the dp[i] = nums[i] + max(0, best previous) transition first shows understanding of the problem. Improving the window maximum using a deque demonstrates strong knowledge of sliding window optimization and queue-based data structures.

Approach 1: Dynamic Programming with Sliding Window Maximum

This approach involves using dynamic programming with a sliding window to maintain the maximum sum at each position. For each position i in the array, calculate the maximum sum that can be achieved till that position, considering the constraint j - i <= k. Use a deque to track the indices which offer the maximum sum within the range of k.

Python

from collections import deque

def constrainedSubsequenceSum(nums, k):
    dp = [0] * len(nums)
    deq = deque()
    dp[0] = nums[0]
    deq.append(0)
    max_sum = nums[0]

    for i in range(1, len(nums)):
        if deq[0] < i - k:
            deq.popleft()
        dp[i] = nums[i] + (dp[deq[0]] if deq else 0)
        max_sum = max(max_sum, dp[i])
        while deq and dp[deq[-1]] <= dp[i]:
            deq.pop()
        deq.append(i)

    return max_sum

nums = [10, 2, -10, 5, 20]
k = 2
print(constrainedSubsequenceSum(nums, k))

Java

import java.util.*;

public class Main {
    public static int constrainedSubsequenceSum(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        int[] dp = new int[nums.length];
        int maxSum = nums[0];
        dp[0] = nums[0];
        deque.add(0);

        for (int i = 1; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peek() < i - k) {
                deque.poll();
            }
            dp[i] = nums[i] + (deque.isEmpty() ? 0 : dp[deque.peek()]);
            maxSum = Math.max(maxSum, dp[i]);
            while (!deque.isEmpty() && dp[deque.getLast()] <= dp[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {10, 2, -10, 5, 20};
        int k = 2;
        System.out.println(constrainedSubsequenceSum(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int constrainedSubsequenceSum(vector<int>& nums, int k) {
    vector<int> dp(nums.size(), 0);
    deque<int> deq;
    int maxSum = nums[0];
    dp[0] = nums[0];
    deq.push_back(0);

    for (int i = 1; i < nums.size(); ++i) {
        if (!deq.empty() && deq.front() < i - k) {
            deq.pop_front();
        }
        dp[i] = nums[i] + (deq.empty() ? 0 : dp[deq.front()]);
        maxSum = max(maxSum, dp[i]);
        while (!deq.empty() && dp[deq.back()] <= dp[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {10, 2, -10, 5, 20};
    int k = 2;
    cout << constrainedSubsequenceSum(nums, k) << endl;
    return 0;
}

JavaScript

function constrainedSubsequenceSum(nums, k) {
    const dp = Array(nums.length).fill(0);
    const deque = [];
    let maxSum = nums[0];
    dp[0] = nums[0];
    deque.push(0);

    for (let i = 1; i < nums.length; i++) {
        if (deque[0] < i - k) deque.shift();
        dp[i] = nums[i] + (deque.length ? dp[deque[0]] : 0);
        maxSum = Math.max(maxSum, dp[i]);
        while (deque.length && dp[deque[deque.length - 1]] <= dp[i]) deque.pop();
        deque.push(i);
    }

    return maxSum;
}

const nums = [10, 2, -10, 5, 20];
const k = 2;
console.log(constrainedSubsequenceSum(nums, k));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int constrainedSubsequenceSum(int* nums, int numsSize, int k) {
    int* dp = malloc(numsSize * sizeof(int));
    int maxSum = INT_MIN;
    int deque[numsSize];
    int front = 0, rear = 0;

    for (int i = 0; i < numsSize; i++) {
        if (front <= rear && deque[front] < i - k) {
            front++;
        }
        dp[i] = nums[i];
        if (front <= rear) {
            dp[i] += dp[deque[front]];
        }
        if (dp[i] > maxSum) {
            maxSum = dp[i];
        }
        while (front <= rear && dp[deque[rear]] <= dp[i]) {
            rear--;
        }
        deque[++rear] = i;
    }

    free(dp);
    return maxSum;
}

int main() {
    int nums[] = {10, 2, -10, 5, 20};
    int k = 2;
    printf("%d\n", constrainedSubsequenceSum(nums, 5, k));
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static int ConstrainedSubsequenceSum(int[] nums, int k) {
        LinkedList<int> deque = new LinkedList<int>();
        int[] dp = new int[nums.Length];
        int maxSum = nums[0];
        dp[0] = nums[0];
        deque.AddLast(0);

        for (int i = 1; i < nums.Length; i++) {
            if (deque.First.Value < i - k) {
                deque.RemoveFirst();
            }
            dp[i] = nums[i] + (deque.Count == 0 ? 0 : dp[deque.First.Value]);
            maxSum = Math.Max(maxSum, dp[i]);
            while (deque.Count > 0 && dp[deque.Last.Value] <= dp[i]) {
                deque.RemoveLast();
            }
            deque.AddLast(i);
        }

        return maxSum;
    }

    static void Main(string[] args) {
        int[] nums = { 10, 2, -10, 5, 20 };
        int k = 2;
        Console.WriteLine(ConstrainedSubsequenceSum(nums, k));
    }
}

Here, Python uses a deque and list to find the maximum subsequence sum. The deque aids in maintaining a list of potential max sums efficiently.

Complexity

Time Complexity: O(n). The space complexity, due to the dp list and deque, is O(n).

Try this approach in the editor

Approach 2: Dynamic Programming with Priority Queue (Heap)

By using a priority queue (or heap), we manage the maximum possible sum within the constraint more efficiently. We employ dynamic programming to calculate the possible maximal sum at each index while maintaining a priority queue to keep track of the relevant maximum sums.

Python

import heapq

def constrainedSubsequenceSum(nums, k):
    maxHeap = []
    heapq.heappush(maxHeap, (-nums[0], 0))
    dp = nums[:]
    max_sum = nums[0]

    for i in range(1, len(nums)):
        while maxHeap and maxHeap[0][1] < i - k:
            heapq.heappop(maxHeap)

        dp[i] = nums[i] - maxHeap[0][0] if maxHeap else nums[i]

        heapq.heappush(maxHeap, (-dp[i], i))
        max_sum = max(max_sum, dp[i])

    return max_sum

nums = [10, 2, -10, 5, 20]
k = 2
print(constrainedSubsequenceSum(nums, k))

Java

import java.util.*;

public class Main {
    public static int constrainedSubsequenceSum(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        maxHeap.add(new int[]{nums[0], 0});
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            while (!maxHeap.isEmpty() && maxHeap.peek()[1] < i - k) {
                maxHeap.poll();
            }
            dp[i] = nums[i] + (maxHeap.isEmpty() ? 0 : maxHeap.peek()[0]);
            maxHeap.add(new int[]{dp[i], i});
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {10, 2, -10, 5, 20};
        int k = 2;
        System.out.println(constrainedSubsequenceSum(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int constrainedSubsequenceSum(vector<int>& nums, int k) {
    priority_queue<pair<int, int>> pq;
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    pq.push({nums[0], 0});
    int maxSum = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        while (!pq.empty() && pq.top().second < i - k) {
            pq.pop();
        }
        int sum = nums[i];
        if (!pq.empty()) {
            sum += pq.top().first;
        }
        dp[i] = sum;
        pq.push({dp[i], i});
        maxSum = max(maxSum, dp[i]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {10, 2, -10, 5, 20};
    int k = 2;
    cout << constrainedSubsequenceSum(nums, k) << endl;
    return 0;
}

JavaScript

function constrainedSubsequenceSum(nums, k) {
    const maxHeap = [];
    const dp = Array.from(nums);
    maxHeap.push([nums[0], 0]);
    let maxSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        while (maxHeap.length && maxHeap[0][1] < i - k) {
            maxHeap.shift();
        }
        dp[i] = nums[i] + (maxHeap.length ? maxHeap[0][0] : 0);
        maxSum = Math.max(maxSum, dp[i]);
        while (maxHeap.length && maxHeap[maxHeap.length - 1][0] <= dp[i]) {
            maxHeap.pop();
        }
        maxHeap.push([dp[i], i]);
    }

    return maxSum;
}

const nums = [10, 2, -10, 5, 20];
const k = 2;
console.log(constrainedSubsequenceSum(nums, k));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

// Min-Heap struct definition
struct MinHeapNode {
    int value;
    int index;
};

struct MinHeap {
    struct MinHeapNode* array;
    int size;
    int capacity;
};

// Utility functions for MinHeap
void swap(struct MinHeapNode* a, struct MinHeapNode* b) {
    struct MinHeapNode t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left].value < heap->array[smallest].value)
        smallest = left;

    if (right < heap->size && heap->array[right].value < heap->array[smallest].value)
        smallest = right;

    if (smallest != idx) {
        swap(&heap->array[smallest], &heap->array[idx]);
        minHeapify(heap, smallest);
    }
}

struct MinHeap* initMinHeap(int capacity) {
    struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->array = (struct MinHeapNode*)malloc(capacity * sizeof(struct MinHeapNode));
    return heap;
}

void insertMinHeap(struct MinHeap* heap, int value, int index) {
    if (heap->size == heap->capacity)
        return;

    int i = heap->size;
    heap->size++;
    heap->array[i] = (struct MinHeapNode){value, index};

    while (i != 0 && heap->array[i].value < heap->array[(i - 1) / 2].value) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

bool isHeapNodeValid(struct MinHeapNode node, int limit) {
    return node.index >= limit;
}

struct MinHeapNode extractMin(struct MinHeap* heap, int limit) {
    struct MinHeapNode root = heap->array[0];
    int i = 0;
    while (!isHeapNodeValid(root, limit) && heap->size > 1) {
        heap->array[0] = heap->array[heap->size - 1];
        heap->size--;
        minHeapify(heap, 0);
        root = heap->array[0];
    }
    return root;
}

int constrainedSubsequenceSum(int* nums, int numsSize, int k) {
    int* dp = malloc(numsSize * sizeof(int));
    struct MinHeap* heap = initMinHeap(numsSize);
    int maxSum = INT_MIN;

    insertMinHeap(heap, -nums[0], 0);
    dp[0] = nums[0];
    maxSum = dp[0];

    for (int i = 1; i < numsSize; i++) {
        struct MinHeapNode minNode = extractMin(heap, i - k);
        dp[i] = nums[i] + (minNode.index >= i - k ? -minNode.value : 0);
        maxSum = maxSum > dp[i] ? maxSum : dp[i];
        insertMinHeap(heap, -dp[i], i);
    }

    free(dp);
    free(heap->array);
    free(heap);

    return maxSum;
}

int main() {
    int nums[] = {10, 2, -10, 5, 20};
    int k = 2;
    printf("%d\n", constrainedSubsequenceSum(nums, 5, k));
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static int ConstrainedSubsequenceSum(int[] nums, int k) {
        SortedDictionary<int, List<int>> map = new SortedDictionary<int, List<int>>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
        int[] dp = new int[nums.Length];
        dp[0] = nums[0];
        if (!map.ContainsKey(nums[0])) map[nums[0]] = new List<int>();
        map[nums[0]].Add(0);
        int maxSum = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            if (map.TryGetValue(map.Keys.GetEnumerator().Current, out List<int> indices) && indices[0] < i - k) {
                int v = indices[0];
                if (map[v].Count == 1) map.Remove(v);
                else map[v].RemoveAt(0);
            }

            int maxPrior = map.Keys.GetEnumerator().Current;
            dp[i] = nums[i] + maxPrior;
            if (!map.ContainsKey(dp[i])) map[dp[i]] = new List<int>();
            map[dp[i]].Add(i);
            maxSum = Math.Max(maxSum, dp[i]);
        }

        return maxSum;
    }

    static void Main(string[] args) {
        int[] nums = { 10, 2, -10, 5, 20 };
        int k = 2;
        Console.WriteLine(ConstrainedSubsequenceSum(nums, k));
    }
}

Python implementation leverages the heapq library for priority-queue operations, allowing us to maintain the crucial subsequence sums within the window efficiently.

Complexity

Time Complexity: O(n log k). Space Complexity is O(n) due to the dp array and the max-heap being maintained through the iterative steps.

Try this approach in the editor

Approach 3: Dynamic Programming + Monotonic Queue

We define f[i] to represent the maximum sum of the subsequence ending at nums[i] that meets the conditions. Initially, f[i] = 0, and the answer is max_{0 leq i \lt n} f(i).

We notice that the problem requires us to maintain the maximum value of a sliding window, which is a typical application scenario for a monotonic queue. We can use a monotonic queue to optimize the dynamic programming transition.

We maintain a monotonic queue q that is decreasing from the front to the back, storing the indices i. Initially, we add a sentinel 0 to the queue.

We traverse i from 0 to n - 1. For each i, we perform the following operations:

If the front element q[0] satisfies i - q[0] > k, it means the front element is no longer within the sliding window, and we need to remove the front element from the queue;
Then, we calculate f[i] = max(0, f[q[0]]) + nums[i], which means we add nums[i] to the sliding window to get the maximum subsequence sum;
Next, we update the answer ans = max(ans, f[i]);
Finally, we add i to the back of the queue and maintain the monotonicity of the queue. If f[q[back]] leq f[i], we need to remove the back element until the queue is empty or f[q[back]] > f[i].

The final answer is ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

TypeScript

function constrainedSubsetSum(nums: number[], k: number): number {
    const q = new Deque<number>();
    const n = nums.length;
    q.pushBack(0);
    let ans = nums[0];
    const f: number[] = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        while (i - q.frontValue()! > k) {
            q.popFront();
        }
        f[i] = Math.max(0, f[q.frontValue()!]!) + nums[i];
        ans = Math.max(ans, f[i]);
        while (!q.isEmpty() && f[q.backValue()!]! <= f[i]) {
            q.popBack();
        }
        q.pushBack(i);
    }
    return ans;
}

class Node<T> {
    value: T;
    next: Node<T> | null;
    prev: Node<T> | null;

    constructor(value: T) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class Deque<T> {
    private front: Node<T> | null;
    private back: Node<T> | null;
    private size: number;

    constructor() {
        this.front = null;
        this.back = null;
        this.size = 0;
    }

    pushFront(val: T): void {
        const newNode = new Node(val);
        if (this.isEmpty()) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.next = this.front;
            this.front!.prev = newNode;
            this.front = newNode;
        }
        this.size++;
    }

    pushBack(val: T): void {
        const newNode = new Node(val);
        if (this.isEmpty()) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.prev = this.back;
            this.back!.next = newNode;
            this.back = newNode;
        }
        this.size++;
    }

    popFront(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        const value = this.front!.value;
        this.front = this.front!.next;
        if (this.front !== null) {
            this.front.prev = null;
        } else {
            this.back = null;
        }
        this.size--;
        return value;
    }

    popBack(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        const value = this.back!.value;
        this.back = this.back!.prev;
        if (this.back !== null) {
            this.back.next = null;
        } else {
            this.front = null;
        }
        this.size--;
        return value;
    }

    frontValue(): T | undefined {
        return this.front?.value;
    }

    backValue(): T | undefined {
        return this.back?.value;
    }

    getSize(): number {
        return this.size;
    }

    isEmpty(): boolean {
        return this.size === 0;
    }
}

func constrainedSubsetSum(nums []int, k int) int {
	q := Deque{}
	q.PushFront(0)
	n := len(nums)
	f := make([]int, n)
	ans := nums[0]
	for i, x := range nums {
		for i-q.Front() > k {
			q.PopFront()
		}
		f[i] = max(0, f[q.Front()]) + x
		ans = max(ans, f[i])
		for !q.Empty() && f[q.Back()] <= f[i] {
			q.PopBack()
		}
		q.PushBack(i)
	}
	return ans
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
	return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
	return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
	q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
	q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
	if len(q.l) > 0 {
		q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
	} else {
		v, q.r = q.r[0], q.r[1:]
	}
	return
}

func (q *Deque) PopBack() (v int) {
	if len(q.r) > 0 {
		q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
	} else {
		v, q.l = q.l[0], q.l[1:]
	}
	return
}

func (q Deque) Front() int {
	if len(q.l) > 0 {
		return q.l[len(q.l)-1]
	}
	return q.r[0]
}

func (q Deque) Back() int {
	if len(q.r) > 0 {
		return q.r[len(q.r)-1]
	}
	return q.l[0]
}

func (q Deque) Get(i int) int {
	if i < len(q.l) {
		return q.l[len(q.l)-1-i]
	}
	return q.r[i-len(q.l)]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Sliding Window Maximum	Time Complexity: O(n). The space complexity, due to the dp list and deque, is O(n).
Dynamic Programming with Priority Queue (Heap)	Time Complexity: O(n log k). Space Complexity is O(n) due to the dp array and the max-heap being maintained through the iterative steps.
Dynamic Programming + Monotonic Queue	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Window Scan	O(nk)	O(n)	Conceptual baseline to understand the DP transition
DP with Priority Queue (Heap)	O(n log k)	O(n)	When a heap is easier to implement than a deque
DP with Monotonic Deque (Sliding Window Maximum)	O(n)	O(n)	Optimal solution for large inputs and typical interview expectation

Frequently asked questions

Is Constrained Subsequence Sum easy or hard?

Constrained Subsequence Sum is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the DP transition and optimizing the sliding window maximum using a monotonic deque or heap to avoid O(nk) time.

Constrained Subsequence Sum Python/Java solution

Python and Java implementations typically use dynamic programming with either a deque or a priority queue. The deque-based approach achieves O(n) time by maintaining a decreasing sequence of DP values, while the heap-based approach runs in O(n log k). Both implementations follow the same DP recurrence.

How to solve Constrained Subsequence Sum in O(n)?

Use dynamic programming with a monotonic deque to track the maximum dp value in the previous k positions. For each index i, compute dp[i] = nums[i] + max(0, dp at deque front). Remove indices outside the window and maintain decreasing order by removing smaller values from the back. Each index is processed once, producing linear time.

What is the best approach for Constrained Subsequence Sum?

The optimal approach uses dynamic programming with a monotonic deque to maintain the maximum DP value within the last k indices. Each step computes dp[i] = nums[i] + max(0, best previous dp in window). The deque keeps values in decreasing order so the maximum is always available in O(1). This reduces the overall complexity to O(n) time and O(n) space.

Is Constrained Subsequence Sum asked at Google/Amazon/Meta?

Constrained Subsequence Sum is a common hard dynamic programming interview problem and variations have appeared in interviews at companies like Google, Amazon, and Meta. The question tests DP transitions, sliding window optimization, and data structure knowledge such as heaps or monotonic queues.

What data structure is used in Constrained Subsequence Sum?

The optimal solution uses a monotonic deque (double-ended queue) to maintain the maximum DP value inside a sliding window. Alternative solutions use a max heap or priority queue to track the best candidate within the last k indices.

What is the time complexity of Constrained Subsequence Sum?

The optimal solution runs in O(n) time using a monotonic deque that maintains the maximum DP value within a sliding window of size k. Each element is inserted and removed from the deque at most once. Alternative implementations using a heap take O(n log k) time.

Constrained Subsequence Sum solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Sliding Window Maximum

Approach 2: Dynamic Programming with Priority Queue (Heap)

Approach 3: Dynamic Programming + Monotonic Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Constrained Subsequence Sum solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Sliding Window Maximum

Approach 2: Dynamic Programming with Priority Queue (Heap)

Approach 3: Dynamic Programming + Monotonic Queue

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems