3180. 执行操作可获得的最大总奖励 I

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。

 

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

 

提示：

1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000

/*
 * @lc app=leetcode.cn id=3180 lang=golang
 * @lcpr version=30204
 *
 * [3180] 执行操作可获得的最大总奖励 I
 */
func maxTotalReward(rewardValues []int) int {

	sort.Ints(rewardValues)

	// 好赖皮的算法, dp[i]表示最大的奖励是否可获取, n表示长度,m表示最大值 , 那么排序后, 最大的奖励就是 2*dp[n-1] + 1
	// dp[i], 其中的i是value

	n := len(rewardValues)

	m := rewardValues[n-1]

	dp := make([]int, 2*m)

	dp[0] = 1 // 从0开始

	for _, value := range rewardValues {
		for i := 2*value - 1; i >= value; i-- { // 对于每个value, 最大值是 2*value - 1
			if dp[i-value] == 1 { // 如果减去这个值可以获取, 那么加上这个值也能获取
				dp[i] = 1 // 不断减value, 更新可获取到的值
			}
		}
	}

	res := 0

	for i := 0; i < len(dp); i++ {
		if dp[i] == 1 {
			res = i
		}
	}
	return res
}