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}

1