Maximum Balanced Subsequence Sum
You are given a 0-indexed integer array nums.
A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds:
nums[ij] - nums[ij-1] >= ij - ij-1, for everyjin the range[1, k - 1].
A subsequence of nums having length 1 is considered balanced.
Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums.
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.
Example 1
Input
nums = [3,3,5,6]Output
14The subsequence
[3, 5, 6] at indices 0, 2, and 3 is balanced and has the maximum possible sum of 14.Example 2
Input
nums = [5,-1,-3,8]Output
13The subsequence
[5, 8] at indices 0 and 3 is balanced and has the maximum possible sum of 13.Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9