Maximum Balanced Subsequence Sum

This approach uses dynamic programming to solve the problem. First, we transform the problem's condition. The condition nums[i_j] - nums[i_{j-1}] >= i_j - i_{j-1} can be rewritten as nums[i_j] - i_j >= nums[i_{j-1}] - i_{j-1}. Let's define a new array b where b[i] = nums[i] - i. The problem now is to find a subsequence with non-decreasing b values that has the maximum sum of corresponding nums values.

We define dp[i] as the maximum sum of a balanced subsequence ending at index i. To compute dp[i], we look at all previous indices j < i. If b[j] <= b[i], it means we can extend a balanced subsequence ending at j with the element at i. We choose the j that gives the maximum dp[j] to maximize the new sum.

• Create a dp array of size n, where n is the length of nums.
• Initialize a variable max_sum to the smallest possible long value.
• Loop i from 0 to n-1:
  • Initialize maxPrevSum = 0.
  • Loop j from 0 to i-1:
    • If (long)nums[j] - j <= (long)nums[i] - i, update maxPrevSum = Math.max(maxPrevSum, dp[j]).
  • Set dp[i] = nums[i] + maxPrevSum.
  • Update max_sum = Math.max(max_sum, dp[i]).
• Return max_sum.

The recurrence relation is dp[i] = nums[i] + max({0} U {dp[j] | 0 <= j < i and b[j] <= b[i]}), where b[k] = nums[k] - k. We iterate through each element of the array from left to right. For each element nums[i], we calculate the maximum possible sum of a balanced subsequence ending at this index. This is done by finding the maximum sum of a valid preceding subsequence and adding nums[i] to it. A preceding subsequence ending at index j is valid if j < i and nums[j] - j <= nums[i] - i. If no such valid preceding subsequence exists or if all of them have a sum less than or equal to zero, we can start a new subsequence with just nums[i], which means we add 0 to nums[i].

The algorithm is as follows:

1. Create an array dp of the same size as nums, where dp[i] will store the maximum sum of a balanced subsequence ending at index i.
2. Iterate through the nums array with index i from 0 to n-1.
3. For each i, initialize a variable maxPrevSum to 0.
4. Start an inner loop with index j from 0 to i-1.
5. Inside the inner loop, check if the balanced condition is met: (long)nums[j] - j <= (long)nums[i] - i.
6. If the condition is met, update maxPrevSum = Math.max(maxPrevSum, dp[j]).
7. After the inner loop, calculate dp[i] = nums[i] + maxPrevSum.
8. The final answer is the maximum value found in the dp array.

import java.util.Arrays;

class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        long[] dp = new long[n];
        long maxSum = Long.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            long maxPrevSum = 0;
            for (int j = 0; j < i; j++) {
                if ((long)nums[j] - j <= (long)nums[i] - i) {
                    maxPrevSum = Math.max(maxPrevSum, dp[j]);
                }
            }
            dp[i] = (long)nums[i] + maxPrevSum;
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }
}