1425. Constrained Subsequence Sum Hard

1/**
2 * [1425] Constrained Subsequence Sum
3 *
4 * 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.
5 * 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.
6 *  
7 * Example 1:
8 * 
9 * Input: nums = [10,2,-10,5,20], k = 2
10 * Output: 37
11 * Explanation: The subsequence is [10, 2, 5, 20].
12 * 
13 * Example 2:
14 * 
15 * Input: nums = [-1,-2,-3], k = 1
16 * Output: -1
17 * Explanation: The subsequence must be non-empty, so we choose the largest number.
18 * 
19 * Example 3:
20 * 
21 * Input: nums = [10,-2,-10,-5,20], k = 2
22 * Output: 23
23 * Explanation: The subsequence is [10, -2, -5, 20].
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	1 <= k <= nums.length <= 10^5
29 * 	-10^4 <= nums[i] <= 10^4
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/constrained-subsequence-sum/
35// discuss: https://leetcode.com/problems/constrained-subsequence-sum/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn constrained_subset_sum(nums: Vec<i32>, k: i32) -> i32 {
41        0
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_1425() {
53    }
54}
55