hard Constrained Subsequence Sum

Problem Statement

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

A subsequence of the array is obtained by removing some elements (may be zero) from the array, leaving the remaining elements in their original order.

Examples

Example 1:

• Input: arr = [10, -2, -10, 5], k = 2
• Expected Output: 13
• Explanation: The subsequence [10, -2, 5] has a maximum sum 13, which follows the given rules.

Example 2:

• Input: arr = [3, 2, 1, -5], k = 1
• Expected Output: 6
• Explanation: The subsequence [3, 2, 1] has a maximum sum, which follows the given rules.

Example 3:

• Input: arr = [3, 2, 7, -5, 10], k = 2
• Expected Output: 22
• Explanation: The optimal subsequence to choose is [3, 2, 7, 10]. Starting with 3, then pick 2 and 7, and finally, skip -5(negative number) and pick 10, resulting in the maximum sum of 22.

Solution

To solve this problem, we'll leverage a dynamic programming approach with a sliding window technique, enhanced by a deque to efficiently manage the k constraint. The essence of our approach is to maintain a list of potential candidates for each position in a way that allows us to quickly find the maximum sum up to that point, considering the constraint that we cannot pick two elements greater than k positions apart. We believe this approach works effectively because it combines the robustness of dynamic programming in handling subproblems (finding the maximum sum up to each point) with the efficiency of a deque in maintaining the maximum value within the sliding window of the last k elements. This method ensures that we always have quick access to the best candidate for the next step in our sequence, optimizing both time and space usage.

By keeping track of the maximum sums in a dynamic manner and pruning non-viable options using the deque, we ensure that our algorithm remains both efficient and straightforward. The sliding window deque helps us avoid recalculating sums for elements that are too far apart to be included in the same subsequence, thereby significantly reducing the computational overhead. This blend of dynamic programming for subproblem optimization and deque for efficient constraint management makes our approach the most effective for tackling the problem.

Step-by-step algorithm

• Initialize a dynamic array dp of the same length as the input array arr to store the maximum sum up to each index.
• Initialize a deque to maintain the indices of potential candidates for the maximum sum, ensuring that the deque always represents the best choices within the last k elements.
• Iterate through arr, and for each element at index i:
  • Calculate dp[i] as the maximum of arr[i] and arr[i] + dp[deque.front()], which represents either taking the current element by itself or adding it to the sum of the best subsequence ending k or less elements before.
  • While the deque is not empty and dp[i] is greater than dp[deque.back()], pop elements from the back of the deque. This step ensures that the deque always contains the indices of elements that are potential candidates for forming the maximum sum.
  • If any indices in the deque are more than k steps away from i, remove them from the front. This action maintains the constraint that any two elements in the subsequence must be at least k places apart.
  • Push the current index i onto the back of the deque.
• The answer to the problem is the maximum value in the dp array.

Algorithm Walkthrough

Let's consider the input arr = [3, 2, 7, -5, 10] with k = 2.

Initial Setup

• Input Array (arr): [3, 2, 7, -5, 10]
• Constraint (k): 2
• Dynamic Programming Array (dp): Initialized to [0, 0, 0, 0, 0] (same length as arr).
• Deque (dq): An empty deque to keep track of indices with potential maximum sums.

Iteration 1: Index 0 (Value = 3)

• dp[0] is set to arr[0] which is 3. dp = [3, 0, 0, 0, 0].
• Deque is updated to [0].
• Maximum sum so far is 3.

Iteration 2: Index 1 (Value = 2)

• Calculate dp[1]: The deque contains 0 at its front, so dp[1] = max(arr[1], dp[deque.front()] + arr[1]) = max(2, 3 + 2) = 5.
• dp = [3, 5, 0, 0, 0]
• Update deque: dp[1] > dp[0]. So, pop 0 from the queue.
• Deque becomes [1].
• Maximum sum so far is 5.

Iteration 3: Index 2 (Value = 7)

• Calculate dp[2]: The deque contains 1 at its front, so dp[2] = max(arr[2], dp[deque.front()] + arr[2]) = max(7, 5 + 7) = 12.
• dp = [3, 5, 12, 0, 0]
• Update deque: dp[2] > dp[1]. So, pop 1 from the queue.
• Deque becomes [2].
• Maximum sum so far is 12.

Iteration 4: Index 3 (Value = -5)

• Calculate dp[3]: The deque contains 2 at its front, so dp[3] = max(arr[3], dp[deque.front()] + arr[3]) = max(-5, 12 + -5) = 7.
• dp = [3, 5, 12, 7, 0]
• Update deque: dp[3] < dp[2]. So, We don't need to perform the pop operation in the queue.
• Push 3 in the Deque. Deque becomes [2, 3].
• Maximum sum so far is 12.

Iteration 5: Index 4 (Value = 10)

• Calculate dp[4]: The deque contains 1 at its front, so dp[4] = max(arr[4], dp[deque.front()] + arr[4]) = max(10, 12 + 10) = 22.
• dp = [3, 5, 12, 7, 22]
• Update deque: dp[4] > dp[3]. So, pop 3 from the queue.
• Update deque: dp[4] > dp[2]. So, pop 2 from the queue.
• Deque becomes [].
• Maximum sum so far is 22.

Conclusion

• The maximum sum is 22.

Code

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

  public int constrainedSubsetSum(int[] arr, int k) {
    int n = arr.length;
    int[] dp = new int[n];
    Deque<Integer> deque = new LinkedList<>();

    int maxSum = arr[0];
    for (int i = 0; i < n; i++) {
      // If the deque is not empty, add the maximum value in deque to the current element
      dp[i] = arr[i];
      if (!deque.isEmpty()) {
        dp[i] = Math.max(dp[i], dp[deque.peekFirst()] + arr[i]);
      }
      // Update the global maxSum
      maxSum = Math.max(maxSum, dp[i]);

      // Remove elements from the deque that are not in the current window of size k
      while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
        deque.pollFirst();
      }
      // Remove elements that are smaller than the current dp[i] as they are not needed
      while (!deque.isEmpty() && dp[deque.peekLast()] < dp[i]) {
        deque.pollLast();
      }

      deque.offerLast(i);
    }

    return maxSum;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] arr1 = { 10, -2, -10, 5 };
    int k1 = 2;
    System.out.println(
      "Example 1 Output: " + sol.constrainedSubsetSum(arr1, k1)
    ); // Expected Output: 13

    int[] arr2 = { 3, 2, 1, -5 };
    int k2 = 1;
    System.out.println(
      "Example 2 Output: " + sol.constrainedSubsetSum(arr2, k2)
    ); // Expected Output: 6

    int[] arr3 = { 3, 2, 7, -5, 10 };
    int k3 = 2;
    System.out.println(
      "Example 3 Output: " + sol.constrainedSubsetSum(arr3, k3)
    ); // Expected Output: 22
  }
}

Complexity Analysis

Time Complexity

• : The algorithm iterates through each element of the input array exactly once. During each iteration, the operations performed (such as updating the dynamic programming array dp, and adding/removing elements from the deque) are constant time operations, assuming that deque operations (pushBack, popFront, popBack) are O(1). Therefore, the overall time complexity is linear with respect to the length of the input array, n.

Space Complexity

• : The space complexity is primarily dictated by the size of the dynamic programming array dp, which stores the maximum sum that can be obtained up to each index. This array has the same length as the input array, so the space complexity is . Additionally, the deque used for optimizing the search for the maximum within a sliding window can, in the worst case, store an index for each element in the array. However, this does not change the overall space complexity, which remains linear with respect to the input size.