首先想到的是划分dp: dp[i] = max_j((num[i] - num[j] >= i - j)?dp[j]:0) + nums[i], 但这样不可避免的O(n^2)
这类找一对的题首先要将num[i] - num[j] >= i - j 转换成num[i] - i >= num[j] - j
让数组b[i] = num[i] - i, 那我们的目标就简化成了 找到b[i] >= b[j]. 在此基础上我们再将b 排序并离散化,即最小的数改成1,第二小的数改成2,依次类推,这样的更改并不影响原来的属性。
这样我们发现,对于第j位 都可以把j加入subsequence里