1using System;
2using System.Collections.Generic;
3
4class Program {
5    public static int ConstrainedSubsequenceSum(int[] nums, int k) {
6        LinkedList<int> deque = new LinkedList<int>();
7        int[] dp = new int[nums.Length];
8        int maxSum = nums[0];
9        dp[0] = nums[0];
10        deque.AddLast(0);
11
12        for (int i = 1; i < nums.Length; i++) {
13            if (deque.First.Value < i - k) {
14                deque.RemoveFirst();
15            }
16            dp[i] = nums[i] + (deque.Count == 0 ? 0 : dp[deque.First.Value]);
17            maxSum = Math.Max(maxSum, dp[i]);
18            while (deque.Count > 0 && dp[deque.Last.Value] <= dp[i]) {
19                deque.RemoveLast();
20            }
21            deque.AddLast(i);
22        }
23
24        return maxSum;
25    }
26
27    static void Main(string[] args) {
28        int[] nums = { 10, 2, -10, 5, 20 };
29        int k = 2;
30        Console.WriteLine(ConstrainedSubsequenceSum(nums, k));
31    }
32}

1