题目描述：
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.
A 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
题目大意：
带约束条件的最大子序列和。约束条件为子序列中人一个两个相邻元素在原始序列中下标的距离不超过k。
解题思路：
动态规划（Dynamic Programming）
状态转移方程为：dp[i] = max(dp[j], 0) + nums[i] 其中j ∈ [i - k, i)
朴素解法的时间复杂度O(N ^ 2)，由于数组长度和k的规模为10^5，可能会超时。
O(N * log N) 解法：TreeMap
使用TreeMap可以将时间复杂度优化到O(N * log N)。
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();
}
}
O(N)解法： 双端队列 (deque)
利用双端队列维护滑动窗口
详情参阅解题报告 Sliding Window Maximum
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)
本文链接：http://bookshadow.com/weblog/2020/05/04/leetcode-constrained-subsequence-sum/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
