#2926
Maximum Balanced Subsequence Sum
international master · 2080 · lc hard +32 · failed · 25.8% accepted · 290 likes · top 4%
Description
You are given a 0-indexed integer array nums.
A subsequence at indices i0 < i1 < ... < ik-1 is balanced when every consecutive pair satisfies nums[ij] - nums[ij-1] >= ij - ij-1. Any single-element subsequence is automatically balanced.
Return the maximum element sum achievable by a balanced subsequence of nums.
A subsequence is any non-empty subset of elements preserving their original order.
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.
Code
1
2
3