Formatted question description: https://leetcode.ca/all/1425.html
1425. Constrained Subsequence Sum (Hard)
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
Related Topics:
Dynamic Programming
Solution 1. DP
If all the elements in A are zero or negative, the result is just the maximum value.
Otherwise, let dp[i] be the maximum result I can get on the subarray A[0..i] if I pick A[i].
The result is max(dp[i] | 0 <= i < N).
For dp[i], since we picked A[i], the previous pick must be one of A[i-k], A[i-k+1], …, A[i-1].
So dp[i] = A[i] + max( dp[j] | i-k <= j < i ).
Here is a TLE version.
// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Time: O(NK)
// Space: O(N)
// NOTE: this will get TLE
class Solution {
public:
int constrainedSubsetSum(vector<int>& A, int k) {
int maxVal = *max_element(begin(A), end(A));
if (maxVal <= 0) return maxVal;
int N = A.size(), ans = 0;
vector<int> dp(N);
for (int i = 0; i < N; ++i) {
int mx = 0;
for (int j = 1; j <= k; ++j) {
if (i - j < 0) break;
mx = max(mx, dp[i - j]);
}
dp[i] = mx + A[i];
ans = max(ans, dp[i]);
}
return ans;
}
};
One optimization is that we can break the j loop once A[i - j] > 0, because further extending j won’t give us better result.
// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Time: O(NK)
// Space: O(N)
class Solution {
public:
int constrainedSubsetSum(vector<int>& A, int k) {
int maxVal = *max_element(begin(A), end(A));
if (maxVal <= 0) return maxVal;
int N = A.size(), ans = 0;
vector<int> dp(N);
for (int i = 0; i < N; ++i) {
int mx = 0;
for (int j = 1; j <= k; ++j) {
if (i - j < 0) break;
mx = max(mx, dp[i - j]);
if (A[i - j] > 0) break;
}
dp[i] = mx + A[i];
ans = max(ans, dp[i]);
}
return ans;
}
};
Solution 2. DP + multiset
Same idea as Solution 1, here we use a multiset to prevent linear search of the maximum dp value.
// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Time: O(NlogK)
// Space: O(N)
class Solution {
public:
int constrainedSubsetSum(vector<int>& A, int k) {
int maxVal = *max_element(begin(A), end(A));
if (maxVal <= 0) return maxVal;
int N = A.size(), ans = 0;
multiset<int> s{0};
vector<int> dp(N);
for (int i = 0; i < N; ++i) {
int sum = *s.rbegin() + A[i];
if (i >= k) s.erase(s.find(dp[i - k]));
s.insert(sum);
dp[i] = sum;
ans = max(ans, sum);
}
return ans;
}
};
Solution 3. DP + Monotonous Deque
Assume the dp values are 3, 1, 2. Popping 3 will change the max value, but popping 1 won’t. This tells us that we can just keep the 3, 2 dp sequence which forms a monotonically decreasing sequence.
We can store the indexes of these sequence in a deque<int> mx. dp[mx.front()] stores the maximum dp value within the dp[i-k] and dp[i-1] range.
dp[i] = max(0, dp[mx.front()]) + A[i]
Given dp[i], we can pop those indexes in mx which are pointing to dp values that are smaller or equal todp[i].
Then we can push i into the mx deque.
Don’t forget popping the out-of-range index, i.e. when mx.front() === i - k - 1, we should pop front.
// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int constrainedSubsetSum(vector<int>& A, int k) {
int maxVal = *max_element(begin(A), end(A));
if (maxVal <= 0) return maxVal;
int N = A.size(), ans = 0;
deque<int> mx;
vector<int> dp(N);
for (int i = 0; i < N; ++i) {
if (mx.size() && mx.front() == i - k - 1) mx.pop_front();
dp[i] = max(0, mx.size() ? dp[mx.front()] : 0) + A[i];
while (mx.size() && dp[mx.back()] <= dp[i]) mx.pop_back();
mx.push_back(i);
ans = max(ans, dp[i]);
}
return ans;
}
};
Solution 4. DP + Monotonous Deque
// OJ: https://leetcode.com/problems/constrained-subsequence-sum/
// Time: O(N)
// Space: O(K)
// Ref: https://leetcode.com/problems/constrained-subsequence-sum/discuss/597751/JavaC%2B%2BPython-O(N)-Decreasing-Deque
class Solution {
public:
int constrainedSubsetSum(vector<int>& A, int k) {
deque<int> q;
int ans = A[0];
for (int i = 0; i < A.size(); ++i) {
A[i] += q.size() ? q.front() : 0;
ans = max(ans, A[i]);
while (q.size() && A[i] > q.back()) q.pop_back();
if (A[i] > 0) q.push_back(A[i]);
if (i >= k && q.size() && q.front() == A[i - k]) q.pop_front();
}
return ans;
}
};
Java
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
int length = nums.length;
int max = nums[0];
for (int i = 1; i < length; i++)
max = Math.max(max, nums[i]);
if (max <= 0)
return max;
if (k == length)
k--;
ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
deque.addLast(0);
int[][] dp = new int[length][2];
dp[0][0] = nums[0];
dp[0][1] = 0;
for (int i = 1; i <= k; i++) {
int num = nums[i];
dp[i][0] = Math.max(num, dp[deque.getFirst()][0] + num);
while (!deque.isEmpty() && dp[deque.getLast()][0] < dp[i][0])
deque.removeLast();
deque.addLast(i);
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
for (int i = k + 1; i < length; i++) {
if (!deque.isEmpty() && deque.getFirst() == i - k - 1)
deque.removeFirst();
int num = nums[i];
dp[i][0] = Math.max(num, dp[deque.getFirst()][0] + num);
while (!deque.isEmpty() && dp[deque.getLast()][0] < dp[i][0])
deque.removeLast();
deque.addLast(i);
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
return Math.max(dp[length - 1][0], dp[length - 1][1]);
}
}