1425. Constrained Subsequence Sum LeetCode Solution
In this guide, you will get 1425. Constrained Subsequence Sum LeetCode Solution with the best time and space complexity. The solution to Constrained Subsequence Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
1425. Constrained Subsequence Sum LeetCode Solution in C++
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
// dp[i] := the maximum the sum of non-empty subsequences in nums[0..i]
vector<int> dp(nums.size());
// dq stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0
// in decreasing order.
deque<int> dq;
for (int i = 0; i < nums.size(); ++i) {
if (dq.empty())
dp[i] = nums[i];
else
dp[i] = max(dq.front(), 0) + nums[i];
while (!dq.empty() && dq.back() < dp[i])
dq.pop_back();
dq.push_back(dp[i]);
if (i >= k && dp[i - k] == dq.front())
dq.pop_front();
}
return ranges::max(dp);
}
}; /* code provided by PROGIEZ */
1425. Constrained Subsequence Sum LeetCode Solution in Java
class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
// dp[i] := the maximum the sum of non-empty subsequences in nums[0..i]
int[] dp = new int[nums.length];
// dq stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0
// in decreasing order.
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < nums.length; ++i) {
if (dq.isEmpty())
dp[i] = nums[i];
else
dp[i] = Math.max(dq.peekFirst(), 0) + nums[i];
while (!dq.isEmpty() && dq.peekLast() < dp[i])
dq.pollLast();
dq.offerLast(dp[i]);
if (i >= k && dp[i - k] == dq.peekFirst())
dq.pollFirst();
}
return Arrays.stream(dp).max().getAsInt();
}
} // code provided by PROGIEZ
1425. Constrained Subsequence Sum LeetCode Solution in Python
class Solution:
def constrainedSubsetSum(self, nums: list[int], k: int) -> int:
# dp[i] := the maximum the sum of non-empty subsequences in nums[0..i]
dp = [0] * len(nums)
# dq stores dp[i - k], dp[i - k + 1], ..., dp[i - 1] whose values are > 0
# in decreasing order.
dq = collections.deque()
for i, num in enumerate(nums):
if dq:
dp[i] = max(dq[0], 0) + num
else:
dp[i] = num
while dq and dq[-1] < dp[i]:
dq.pop()
dq.append(dp[i])
if i >= k and dp[i - k] == dq[0]:
dq.popleft()
return max(dp) # code by PROGIEZ
