1798.你能构造出连续值的最大数目

问题描述

1798.你能构造出连续值的最大数目

解题思路

贪心+动态规划

首先将数组按升序排序，令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;
    }
};