[C++] O(nlgn) Time, Constant Space DP Solution Explained
I started to tackle this problem in a kind of crude DP fashion (you know, preparing all the cells up to the sum of all the provided coins), when it occurred to 
I started to tackle this problem in a kind of crude DP fashion (you know, preparing all the cells up to the sum of all the provided coins), when it occurred to me that there was a simpler way, less memory demanding way and that is the one I am going to explore and explaing now :)\n\nTo proceed, we will first of all initialise `res`, our usual accumulator variable, to be `1`, since we can always do at least a combination (`0`, no matter what coins are we given).\n\nThe magic starts now: we will sort `coins` so that they are in increasing order, then we will loop through them and for each `coin` we will check if its value is `<` res, which means we could actually get to use it to gain `res + coin` more combinations, since our loop invariant is that we could reach `res` without any gaps. As soon as we find a coin bigger than `res`, it implies that we would have gap, so we quit.\n\nAt the end of the loop, we can just return `res` and be done with it.\n\nLet\'s try with a couple of simple examples, starting with (already sorted) `coins == {1, 1, 4}`.\n\nWe will have initially:\n\n```cpp\nres = 1; // we can reach a value of 0 with the coins\ncoin = 1\n```\n\nSince `coin <= res`, we know that we can reach `res` as a value, so we increase `res` by `1` and we move on:\n\n```cpp\nres = 2; // we can reach a value of 1 with the coins, so we have 2 combinations available\ncoin = 1\n```\n\nAgain, we want to know if we can reach `2` with our coins so far and it turns out we can, since `coins < res`:\n\n```cpp\nres = 3; // we can reach a value of 2 with the coins, so we have 3 possible combinations\ncoin = 4\n```\n\nAnd here we stop, since `coin > res` (`4 > 3`), which means we cannot reach `4` with any of the smaller coins (and of course if we had bigger coins, they would not help either).\n\nIf we had `coins = {1, 1, 1, 4}`, you can easily verify how the last step would lead us to have\n\n```cpp\nres = 4; // we can reach a value of 3 with the coins, so we have 4 valid combinations\ncoin = 4\n```\n\nAnd then we might be able to return `res == 4 + 4 == 8` different combinations; if we had `5` or higher as a last coin, it is easy to visualise how we might have not gone back to a `5` or more cells ago in an ideal DP computation of all the possible combinations with it, not without gaps.\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int getMaximumConsecutive(vector<int>& coins) {\n        // support variables\n        int res = 1;\n        // preparing coins\n        sort(begin(coins), end(coins));\n        for (int coin: coins) {\n            // checking if we could have reached coin without gaps\n            if (res >= coin) res += coin;\n            else break;\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'C', 'Combinatorics', 'C++']