2926. Maximum Balanced Subsequence Sum Hard

1/**
2 * [2926] Maximum Balanced Subsequence Sum
3 *
4 * You are given a 0-indexed integer array nums.
5 * A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds:
6 * 
7 * 	nums[ij] - nums[ij-1] >= ij - ij-1, for every j in the range [1, k - 1].
8 * 
9 * A subsequence of nums having length 1 is considered balanced.
10 * Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums.
11 * A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
12 *  
13 * <strong class="example">Example 1:
14 * 
15 * Input: nums = [3,3,5,6]
16 * Output: 14
17 * Explanation: In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected.
18 * nums[2] - nums[0] >= 2 - 0.
19 * nums[3] - nums[2] >= 3 - 2.
20 * Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
21 * The subsequence consisting of indices 1, 2, and 3 is also valid.
22 * It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.
23 * <strong class="example">Example 2:
24 * 
25 * Input: nums = [5,-1,-3,8]
26 * Output: 13
27 * Explanation: In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected.
28 * nums[3] - nums[0] >= 3 - 0.
29 * Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
30 * It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.
31 * 
32 * <strong class="example">Example 3:
33 * 
34 * Input: nums = [-2,-1]
35 * Output: -1
36 * Explanation: In this example, the subsequence [-1] can be selected.
37 * It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
38 * 
39 *  
40 * Constraints:
41 * 
42 * 	1 <= nums.length <= 10^5
43 * 	-10^9 <= nums[i] <= 10^9
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/maximum-balanced-subsequence-sum/
49// discuss: https://leetcode.com/problems/maximum-balanced-subsequence-sum/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn max_balanced_subsequence_sum(nums: Vec<i32>) -> i64 {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_2926() {
67    }
68}
69