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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int constrainedSubsequenceSum(int* nums, int numsSize, int k) {
6 int* dp = malloc(numsSize * sizeof(int));
7 int maxSum = INT_MIN;
8 int deque[numsSize];
9 int front = 0, rear = 0;
10
11 for (int i = 0; i < numsSize; i++) {
12 if (front <= rear && deque[front] < i - k) {
13 front++;
14 }
15 dp[i] = nums[i];
16 if (front <= rear) {
17 dp[i] += dp[deque[front]];
18 }
19 if (dp[i] > maxSum) {
20 maxSum = dp[i];
21 }
22 while (front <= rear && dp[deque[rear]] <= dp[i]) {
23 rear--;
24 }
25 deque[++rear] = i;
26 }
27
28 free(dp);
29 return maxSum;
30}
31
32int main() {
33 int nums[] = {10, 2, -10, 5, 20};
34 int k = 2;
35 printf("%d\n", constrainedSubsequenceSum(nums, 5, k));
36 return 0;
37}The solution uses a dynamic programming array to store the maximum sum possible up to each index. It utilizes a deque to maintain useful indices that help in calculating the needed maximum sum over the moving window of size k without having to recompute every time.
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#include <vector>
#include <queue>
using namespace std;
int constrainedSubsequenceSum(vector<int>& nums, int k) {
priority_queue<pair<int, int>> pq;
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
pq.push({nums[0], 0});
int maxSum = nums[0];
for (int i = 1; i < nums.size(); ++i) {
while (!pq.empty() && pq.top().second < i - k) {
pq.pop();
}
int sum = nums[i];
if (!pq.empty()) {
sum += pq.top().first;
}
dp[i] = sum;
pq.push({dp[i], i});
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
int main() {
vector<int> nums = {10, 2, -10, 5, 20};
int k = 2;
cout << constrainedSubsequenceSum(nums, k) << endl;
return 0;
}C++ uses a max-heap (priority queue) to track potential maxima. It provides a compact way to check out the maximums across a moving window efficiently.