问题描述
解题思路
贪心+动态规划
首先将数组按升序排序，令res[n]为前n个数所能构造出的连续整数的最大值:
if (coins[i - 1] > res[n - 1] + 1),res[n] = res[n - 1] + coins[i - 1];else,res[n] = res[n - 1];
代码
class Solution {
public:
int getMaximumConsecutive(vector<int>& coins) {
std::sort(coins.begin(), coins.end());
vector<int> res(coins.size() + 1, 0); // 表示前n个数能表示出来的最大值
for (int i = 1; i <= coins.size(); i++) {
if (coins[i - 1] > res[i - 1] + 1)
res[i] = res[i - 1];
else
res[i] = res[i - 1] + coins[i - 1];
}
return res[coins.size()] + 1;
}
};