Sponsored
Sponsored
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.
Time Complexity: O(n), where n is the number of elements in the array nums. The space complexity is O(n) due to the storage of the dp array and deque.
1import java.util.*;
2
3public class Main {
4 public static int constrainedSubsequenceSum(int[] nums, int k) {
5 Deque<Integer> deque = new LinkedList<>();
6 int[] dp = new int[nums.length];
7 int maxSum = nums[0];
8 dp[0] = nums[0];
9 deque.add(0);
10
11 for (int i = 1; i < nums.length; i++) {
12 if (!deque.isEmpty() && deque.peek() < i - k) {
13 deque.poll();
14 }
15 dp[i] = nums[i] + (deque.isEmpty() ? 0 : dp[deque.peek()]);
16 maxSum = Math.max(maxSum, dp[i]);
17 while (!deque.isEmpty() && dp[deque.getLast()] <= dp[i]) {
18 deque.removeLast();
19 }
20 deque.addLast(i);
21 }
22
23 return maxSum;
24 }
25
26 public static void main(String[] args) {
27 int[] nums = {10, 2, -10, 5, 20};
28 int k = 2;
29 System.out.println(constrainedSubsequenceSum(nums, k));
30 }
31}The Java version keeps track of the maximum subsequence sum ending at each index using a dp array and employs a deque to maintain an efficient sliding window maximum.
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.
Time Complexity: O(n log k) primarily due to heap operations. Space Complexity: O(n) is utilized by the dp array and the heap.
1
In Java, we use a priority queue to simulate the heap and quickly access the potential subsequence maxima within each legal window constraint.