526互联

1798.maximum number of consecutive values you can make

发布时间 2023-07-26 16:04:21作者: zwyyy456

Description

1798.maximum-number-of-consecutive-values-you-can-make

Solution

Greedy algorithm + dynamic programming

First, we sort the array in ascending orders. Let res[n] be the maximum value of consecutive integer that we can make by using the first n numbers.

  • if (coins[i - 1] > res[n - 1] + 1), res[n] = res[n - 1] + coins[i - 1];
  • else, res[n] = res[n - 1];

Code

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        std::sort(coins.begin(), coins.end());
        vector<int> res(coins.size() + 1, 0); // maximum integer by first nth numbers
        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;
    }
};