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.
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}This C# solution works similarly to other languages shown above, utilizing a double-ended queue for optimal management of the sliding window maximum calculation.
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.
1using System.Collections.Generic;
class Program {
public static int ConstrainedSubsequenceSum(int[] nums, int k) {
SortedDictionary<int, List<int>> map = new SortedDictionary<int, List<int>>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
int[] dp = new int[nums.Length];
dp[0] = nums[0];
if (!map.ContainsKey(nums[0])) map[nums[0]] = new List<int>();
map[nums[0]].Add(0);
int maxSum = nums[0];
for (int i = 1; i < nums.Length; i++) {
if (map.TryGetValue(map.Keys.GetEnumerator().Current, out List<int> indices) && indices[0] < i - k) {
int v = indices[0];
if (map[v].Count == 1) map.Remove(v);
else map[v].RemoveAt(0);
}
int maxPrior = map.Keys.GetEnumerator().Current;
dp[i] = nums[i] + maxPrior;
if (!map.ContainsKey(dp[i])) map[dp[i]] = new List<int>();
map[dp[i]].Add(i);
maxSum = Math.Max(maxSum, dp[i]);
}
return maxSum;
}
static void Main(string[] args) {
int[] nums = { 10, 2, -10, 5, 20 };
int k = 2;
Console.WriteLine(ConstrainedSubsequenceSum(nums, k));
}
}This C# utilizes a dictionary to maintain the highest attainable sequence sums in their respective windows, enhancing optimization over dynamic windows and constraints.