给你一个整数数组 nums ,你可以对它进行一些操作.
返回你能通过这些操作获得的最大点数.
输出:6
按照题目的意思,你每删除一个nums[i],那就必须删除数组中所有值为nums[i] - 1,nums[i] + 1的所有元素,也就是说:假定数组里面有[3 4 5],如果你删除数字4,那么你会获得4个点数,并删除3和5,最终数组为空.
如果是数组[34445],删除数字4,数组最终剩下[44],所以剩下2个4不妨也一起删了,这样子获得的点数会变得更大.
那我们接下来的问题就是:从0到max中,每删除一个数字可以获得i * all[i]个点数,但是一删除i,你就不能再删除i-1和i + 1,问获得的最大点数是多少?
现在的问题就跟198. 打家劫舍很像了.
假定dp[i]表示从0遍历到i目前能获得的最大点数,可以得到转移条件: