Constrained subsequence sum

Array Dynamic Programming Queue Sliding Window Heap (Priority Queue) Monotonic Queue

56.4% acceptance

Feb 25, 2026

2239

109

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::VecDeque;
impl Solution {
  pub fn constrained_subset_sum(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let n = nums.len();
    let mut dp = vec![0i32; n];
    let mut deque: VecDeque<usize> = VecDeque::new(); // indices of max dp values
    let mut result = i32::MIN;
    for i in 0..n {
      // Remove old indices outside window
      while !deque.is_empty() && *deque.front().unwrap() + k < i {
        deque.pop_front();
      }
      let max_prev = if deque.is_empty() { 0 } else { dp[*deque.front().unwrap()].max(0) };
      dp[i] = nums[i] + max_prev;
      result = result.max(dp[i]);
      // Maintain decreasing deque
      while !deque.is_empty() && dp[*deque.back().unwrap()] <= dp[i] {
        deque.pop_back();
      }
      deque.push_back(i);
    }
    result
  }
}