Scale Engineer

Constrained Subsequence Sum

Hard
#1318Time: O(n * k) - For each element `i` in the input array, we iterate up to `k` previous elements to find the maximum. This results in a nested loop structure.Space: O(n) - We use an auxiliary `dp` array of the same size as the input array.1 company
Patterns
Sliding WindowDynamic Programming
Data structures
ArrayHeap (Priority Queue)QueueMonotonic Queue
Companies
Akuna Capital

Prompt

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 <= 105
  • -104 <= nums[i] <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward dynamic programming solution. We define dp[i] as the maximum sum of a valid subsequence ending at index i. To compute dp[i], we must include nums[i]. The previous element in the subsequence, say nums[j], must satisfy the condition j - i <= k. Therefore, dp[i] is nums[i] plus the maximum dp[j] over the valid range of j (i.e., i - k <= j < i). If all possible previous subsequence sums are negative, it's better to start a new subsequence from nums[i], so we take the maximum of 0 and the previous maximum sum.

Algorithm

  • Initialize a dp array of size n, where n is the length of nums.
  • Initialize a variable maxSum to Integer.MIN_VALUE to keep track of the final result.
  • Iterate through the array with an index i from 0 to n-1:
    • For each i, find the maximum value among the previous k DP states. Let's call this maxPrev. Initialize maxPrev to 0.
    • Iterate with an index j from max(0, i - k) to i - 1.
    • In the inner loop, update maxPrev = Math.max(maxPrev, dp[j]).
    • After the inner loop, calculate dp[i] = nums[i] + maxPrev.
    • Update the overall maximum: maxSum = Math.max(maxSum, dp[i]).
  • After the outer loop finishes, return maxSum.

Walkthrough

We create a dp array of the same size as nums. dp[i] will store the maximum constrained subsequence sum that ends with the element nums[i]. The core of the algorithm is the recurrence relation:

dp[i] = nums[i] + max(0, max(dp[j])) for all j such that i - k <= j < i.

We can implement this by iterating through the nums array from i = 0 to n-1. For each i, we have a nested loop that scans the previous k elements (from j = i-1 down to i-k) to find the maximum dp value in that window. This maximum value is then added to nums[i] to compute dp[i]. The final answer is the maximum value found in the dp array, as the subsequence is not required to end at the last element of the array.

class Solution {    public int constrainedSubsetSum(int[] nums, int k) {        int n = nums.length;        int[] dp = new int[n];        int maxSum = Integer.MIN_VALUE;         for (int i = 0; i < n; i++) {            int maxPrev = 0;            for (int j = Math.max(0, i - k); j < i; j++) {                maxPrev = Math.max(maxPrev, dp[j]);            }            dp[i] = nums[i] + maxPrev;            maxSum = Math.max(maxSum, dp[i]);        }        return maxSum;    }}

Complexity

Time

O(n * k) - For each element `i` in the input array, we iterate up to `k` previous elements to find the maximum. This results in a nested loop structure.

Space

O(n) - We use an auxiliary `dp` array of the same size as the input array.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly models the problem's state transitions.

Cons

  • Highly inefficient for large inputs due to the nested loops.

  • Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms for the given constraints.

Solutions

class Solution {public  int constrainedSubsetSum(int[] nums, int k) {    int n = nums.length;    int[] dp = new int[n];    int ans = Integer.MIN_VALUE;    Deque<Integer> q = new ArrayDeque<>();    for (int i = 0; i < n; ++i) {      if (!q.isEmpty() && i - q.peek() > k) {        q.poll();      }      dp[i] = Math.max(0, q.isEmpty() ? 0 : dp[q.peek()]) + nums[i];      while (!q.isEmpty() && dp[q.peekLast()] <= dp[i]) {        q.pollLast();      }      q.offer(i);      ans = Math.max(ans, dp[i]);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem