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.
1from collections import deque
2
3def constrainedSubsequenceSum(nums, k):
4 dp = [0] * len(nums)
5 deq = deque()
6 dp[0] = nums[0]
7 deq.append(0)
8 max_sum = nums[0]
9
10 for i in range(1, len(nums)):
11 if deq[0] < i - k:
12 deq.popleft()
13 dp[i] = nums[i] + (dp[deq[0]] if deq else 0)
14 max_sum = max(max_sum, dp[i])
15 while deq and dp[deq[-1]] <= dp[i]:
16 deq.pop()
17 deq.append(i)
18
19 return max_sum
20
21nums = [10, 2, -10, 5, 20]
22k = 2
23print(constrainedSubsequenceSum(nums, k))Here, Python uses a deque and list to find the maximum subsequence sum. The deque aids in maintaining a list of potential max sums 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
Python implementation leverages the heapq library for priority-queue operations, allowing us to maintain the crucial subsequence sums within the window efficiently.