Algorithms
Hard
2926
3184
Maximum Balanced Subsequence Sum
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 every j in 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: 14
Explanation: In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected.
nums[2] - nums[0] >= 2 - 0.
nums[3] - nums[2] >= 3 - 2.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
The subsequence consisting of indices 1, 2, and 3 is also valid.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.

Example 2:

Input: nums = [5,-1,-3,8]
Output: 13
Explanation: In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected.
nums[3] - nums[0] >= 3 - 0.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.

Example 3:

Input: nums = [-2,-1]
Output: -1
Explanation: In this example, the subsequence [-1] can be selected.
It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.


Constraints:

 * 1 <= nums.length <= 105
 * -109 <= nums[i] <= 109
"""
class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        
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 every j in 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: 14
Explanation: In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected.
nums[2] - nums[0] >= 2 - 0.
nums[3] - nums[2] >= 3 - 2.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
The subsequence consisting of indices 1, 2, and 3 is also valid.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.

Example 2:

Input: nums = [5,-1,-3,8]
Output: 13
Explanation: In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected.
nums[3] - nums[0] >= 3 - 0.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.

Example 3:

Input: nums = [-2,-1]
Output: -1
Explanation: In this example, the subsequence [-1] can be selected.
It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.


Constraints:

 * 1 <= nums.length <= 105
 * -109 <= nums[i] <= 109


Please complete the code below to solve above prblem:
```python
class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [3,3,5,6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 14

test_input = { "nums": [5,-1,-3,8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 13

test_input = { "nums": [-2,-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [0] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [-47] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -47

test_input = { "nums": [-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -8

test_input = { "nums": [-7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -7

test_input = { "nums": [-6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -6

test_input = { "nums": [-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -5

test_input = { "nums": [-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -3

test_input = { "nums": [-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -2

test_input = { "nums": [-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 1

test_input = { "nums": [3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 3

test_input = { "nums": [4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 8

test_input = { "nums": [9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [45] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 45

test_input = { "nums": [-9,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -5

test_input = { "nums": [-6,8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 8

test_input = { "nums": [-5,-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [-5,0] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [-3,-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [-2,3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 3

test_input = { "nums": [-1,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [-1,0] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [-1,3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 3

test_input = { "nums": [0,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [0,5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [2,7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [5,-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [6,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 6

test_input = { "nums": [7,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [7,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [8,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 8

test_input = { "nums": [9,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [-43,23,-49] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 23

test_input = { "nums": [-9,-6,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -5

test_input = { "nums": [-9,-2,4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [-9,5,-6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [-8,9,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [-5,-1,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [-4,-9,3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 3

test_input = { "nums": [-4,-2,-7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -2

test_input = { "nums": [-3,-4,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -2

test_input = { "nums": [-2,-1,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -1

test_input = { "nums": [-1,-6,1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 1

test_input = { "nums": [0,-6,-4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [0,-5,4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [1,-4,4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [4,1,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [5,-6,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [5,-4,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [6,-3,9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 15

test_input = { "nums": [6,0,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 6

test_input = { "nums": [7,-6,0] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [8,-7,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 8

test_input = { "nums": [14,-21,-18] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 14

test_input = { "nums": [-9,7,-8,1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [-8,2,-5,-7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 2

test_input = { "nums": [-7,1,-2,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 1

test_input = { "nums": [-6,-8,7,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [-5,-1,0,6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 6

test_input = { "nums": [-4,8,9,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 17

test_input = { "nums": [-4,9,7,-4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [-2,-6,0,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [-2,-3,9,3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [0,-6,-3,5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [0,1,0,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 1

test_input = { "nums": [1,-7,-8,6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [3,-7,9,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 12

test_input = { "nums": [3,-7,9,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 12

test_input = { "nums": [4,-8,-1,8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 12

test_input = { "nums": [5,4,1,0] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [7,7,-9,-4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 7

test_input = { "nums": [8,0,4,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 8

test_input = { "nums": [9,7,-2,1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [34,34,32,33] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 65

test_input = { "nums": [-9,-6,-8,-2,4] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [-9,-5,2,2,7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [-9,-2,-6,0,6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 6

test_input = { "nums": [-7,0,-8,-9,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [-7,0,9,-4,9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [-6,-2,-8,-4,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == -2

test_input = { "nums": [-6,2,-3,0,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 2

test_input = { "nums": [-6,3,-6,-3,-2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 3

test_input = { "nums": [-5,-9,1,3,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 4

test_input = { "nums": [-5,1,5,-5,-1] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 6

test_input = { "nums": [-3,7,0,4,6] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 10

test_input = { "nums": [-2,-2,9,-2,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 9

test_input = { "nums": [0,-6,-9,-8,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [0,-2,-7,-1,-8] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [0,-1,-4,-6,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 0

test_input = { "nums": [1,-3,-8,9,-9] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 10

test_input = { "nums": [2,-6,-2,0,-3] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 2

test_input = { "nums": [2,9,-4,4,2] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 11

test_input = { "nums": [4,-1,5,-1,-7] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 5

test_input = { "nums": [4,6,-8,-8,-5] }
assert my_solution.maxBalancedSubsequenceSum(**test_input) == 10