leetcode 1425 - Constrained Subsequence Sum

https://leetcode.com/problems/constrained-subsequence-sum/
https://leetcode.com/problems/constrained-subsequence-sum/discuss/597751/JavaC%2B%2BPython-O(N)-Decreasing-Deque

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int size = nums.size();
int sum = 0;
int max_sum = INT_MIN;
int max_num = INT_MIN;

int i;
int j = 0;

while (j < size) {
if (nums[j] >= 0) {
sum += nums[j];
max_sum = max(max_sum, sum);
j++;
} else {
i = j;

while (j < size && nums[j] < 0) {
max_num = max(max_num, nums[j]);
j++;
}

sum += maxSum(nums, i, j - 1, k);
max_sum = max(max_sum, sum);
sum = max(sum, 0);
}
}

return max_sum < 0 ? max_num : max_sum;
}

int maxSum(vector<int> &nums, int left, int right, int k) {
int size = right - left + 1;
vector<int> dp(size+1);
dp[0] = 0;

if (size < k) return 0;

for (int len = 1; len <= size; len++) {
int max_sum = INT_MIN;
for (int i = len - 1; i >= max(len - k, 0); i--) {
max_sum = max(max_sum, dp[i] + nums[left + len - 1]);
}

dp[len] = max_sum;
}

int max_sum = INT_MIN;
for (int i = 0; i < k; i++) {
max_sum = max(max_sum, dp[size - i]);
}

return max_sum;
}
};

//O(N)
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int size = nums.size();
deque<int> dq;
int max_sum = INT_MIN;

for (int i = 0; i < size; i++) {
nums[i] += dq.empty() ? 0 : dq.front();
max_sum = max(nums[i], max_sum);

while (!dq.empty() && nums[i] > dq.back())
dq.pop_back();

if (nums[i] > 0)
dq.push_back(nums[i]);

if (i >= k && !dq.empty() && dq.front() == nums[i-k])
dq.pop_front();
}

return max_sum;
}
};