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.
1#include <iostream>
2#include <vector>
3#include <deque>
4using namespace std;
5
6int constrainedSubsequenceSum(vector<int>& nums, int k) {
7 vector<int> dp(nums.size(), 0);
8 deque<int> deq;
9 int maxSum = nums[0];
10 dp[0] = nums[0];
11 deq.push_back(0);
12
13 for (int i = 1; i < nums.size(); ++i) {
14 if (!deq.empty() && deq.front() < i - k) {
15 deq.pop_front();
16 }
17 dp[i] = nums[i] + (deq.empty() ? 0 : dp[deq.front()]);
18 maxSum = max(maxSum, dp[i]);
19 while (!deq.empty() && dp[deq.back()] <= dp[i]) {
20 deq.pop_back();
21 }
22 deq.push_back(i);
23 }
24
25 return maxSum;
26}
27
28int main() {
29 vector<int> nums = {10, 2, -10, 5, 20};
30 int k = 2;
31 cout << constrainedSubsequenceSum(nums, k) << endl;
32 return 0;
33}This solution implements a C++ version using vectors and deques. The deque keeps track of indices with potential maximum sums, helping compute the current index's maximum sum efficiently.
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.