Description Link to heading

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

Solution Link to heading

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 Link to heading 

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;
    }
};