1. 解题思路
这一题的话思路上依然还是动态规划的思路，核心的迭代关系式如下：
def dp(idx, pre_sum) :
if nums[idx] <= pre_sum:
return dp(idx+1, pre_sum)
else:
return max(dp(idx+1, pre_sum), dp(idx+1, nums[idx] + pre_sum))
当然，直接这么实现的话还是会遇到内存爆炸的问题，因此我们需要进一步对这个递推式进行拉平，具体来说就是实现存储下来pre_num，然后每次进行一次for循环遍历，在目标区间内更新取到每一个idx上的值的情况下pre_num的变化。
但是这样的话依然遇到了超时的问题。
后来看了一下别人的解答之后发现，他们的思路很多也差不多是这样，但是做了一些剪枝，具体来说，如果存在两个不同的数相加能够获得max(nums)-1，那么最优解必为2*max(nums)-1，这个用归纳法稍微想想就行了。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def maxTotalReward(self, rewardValues: List[int]) -> int:
rewardValues = sorted(set(rewardValues))
prev = [0]
unseen = [i+1 for i in range(max(rewardValues))]
def in_sorted_list(nums, val):
idx = bisect.bisect_left(nums, val)
return idx if idx <= len(nums) and nums[idx] == val else -1
ans = 0
for reward in rewardValues:
if reward != rewardValues[-1] - reward-1 and in_sorted_list(rewardValues, rewardValues[-1] - reward-1) != -1:
return 2*rewardValues[-1]-1
idx = bisect.bisect_left(prev, reward)-1
ans = max(ans, reward + prev[idx])
i = bisect.bisect_left(unseen, reward)
while i < len(unseen):
if unseen[i] >= 2 * reward:
break
k = in_sorted_list(prev, unseen[i]-reward)
if k == -1:
i += 1
else:
bisect.insort(prev, unseen[i])
unseen.pop(i)
return ans
提交代码评测得到：耗时716ms，占用内存25.1MB。
