Let dp[x] represent the maximum sum of a balanced subsequence ending at x.
提示 2
Rewriting the formula nums[ij] - nums[ij-1] >= ij - ij-1 gives nums[ij] - ij >= nums[ij-1] - ij-1.
提示 3
So, for some index x, we need to find an index y, y < x, such that dp[x] = nums[x] + dp[y] is maximized, and nums[x] - x >= nums[y] - y.
提示 4
There are many ways to achieve this. One method involves sorting the values of nums[x] - x for all indices x and using a segment/Fenwick tree with coordinate compression.
提示 5
Hence, using a dictionary or map, let's call it dict, where dict[nums[x] - x] represents the position of the value, nums[x] - x, in the segment tree.
提示 6
The tree is initialized with zeros initially.
提示 7
For indices x in order from [0, n - 1], dp[x] = max(nums[x], nums[x] + the maximum query from the tree in the range [0, dict[nums[x] - x]]), and if dp[x] is greater than the value in the tree at position dict[nums[x] - x], we update the value in the tree.
提示 8
The answer to the problem is the maximum value in dp.
