给你一个整数数组 nums
和一个整数 k
,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i]
和 nums[j]
,它们在原数组中的下标 i
和 j
满足 i < j
且 j - i <= k
。
数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。
示例 1:
输入:nums = [10,2,-10,5,20], k = 2 输出:37 解释:子序列为 [10, 2, 5, 20] 。
示例 2:
输入:nums = [-1,-2,-3], k = 1 输出:-1 解释:子序列必须是非空的,所以我们选择最大的数字。
示例 3:
输入:nums = [10,-2,-10,-5,20], k = 2 输出:23 解释:子序列为 [10, -2, -5, 20] 。
提示:
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
Time O(N)
Space O(K)
c++
class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { deque<int> q;//Keep a decreasing deque int res=nums[0];//the maximum result you can get if the last element is A[i] for(int i=0;i<nums.size();i++){ //deque[0] is the maximum result in the last element of result.If deque[0] > 0, we add it to nums[i] if(!q.empty())nums[i]+=q.front(); res=max(res,nums[i]); while(!q.empty()&&nums[i]>q.back()) q.pop_back(); if(nums[i]>0)q.push_back(nums[i]); if(i>=k&&!q.empty()&&q.front()==nums[i-k]) q.pop_front(); } return res; } };
py
class Solution: def constrainedSubsetSum(self, nums: List[int], k: int) -> int: deque=collections.deque() for i in range(len(nums)): if deque: nums[i]+=deque[0] while deque and nums[i]>deque[-1]: deque.pop() if nums[i]>0: deque.append(nums[i]) if i>=k and deque and deque[0]==nums[i-k]: deque.popleft() return max(nums)
Java
class Solution { public int constrainedSubsetSum(int[] nums, int k) { Deque<Integer> q=new ArrayDeque<>(); int res=nums[0]; for(int i=0;i<nums.length;i++){ if(!q.isEmpty())nums[i]+=q.peek(); res=Math.max(res,nums[i]); while(!q.isEmpty()&&nums[i]>q.peekLast()) q.pollLast(); if(nums[i]>0)q.offer(nums[i]); if(i>=k&&!q.isEmpty()&&q.peek()==nums[i-k]) q.poll(); } return res; } }