## 题目描述：

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

## 解题思路：

### O(N * log N) 解法：TreeMap

TreeMap维护滑动窗口dp[i - k .. i)范围内的最大值。

### Java代码：

class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
TreeMap<Integer, Integer> big = new TreeMap<>();
int[] dp = nums.clone();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && big.lastKey() > 0) {
dp[i] += big.lastKey();
}
big.put(dp[i], big.getOrDefault(dp[i], 0) + 1);
if (i >= k) {
int cnt = big.get(dp[i - k]) - 1;
if (cnt == 0) {
big.remove(dp[i - k]);
} else {
big.put(dp[i - k], cnt);
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
}

## Python代码：

class Solution(object):
def constrainedSubsetSum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
deque = collections.deque()
dp = []
for i, n in enumerate(nums):
if deque and deque[-1] < i - k: deque.pop()
n += max(0, deque and dp[deque[-1]] or 0)
dp.append(n)
while deque and dp[deque[0]] <= n:
deque.popleft()
deque.appendleft(i)
return max(dp)

Pingbacks已关闭。