✅Short & Easy w/ Explanation | Greedy Approach
We can understand this algorithm through an example. \nIf we have coins [1], we can form the sequence 0, 1. For extending sequence we need coin <= 2.\nIf we hav
We can understand this algorithm through an example. \nIf we have coins `[1]`, we can form the sequence `0, 1`. For extending sequence we need coin <= 2.\nIf we have coing `[1, 2]`, we can form `0, 1, 2, 3`. For extending sequence we need coin <= 4.\nIf we have coing `[1, 2, 3]`, we can form `0, 1, 2, 3, 4, 5, 6`. For extending sequence we need coin <= 7.\nIn each of the above case, ***if the next coin we get is greater than the maximum sequence currently formed, we cannot extend the sequence in any case whatsoever***.\n\nSuppose we get another 1 coin and have `[1,1,2,3]`, we can form `0, 1, 2, 3, 4, 5, 6, 7`. \nWe can see we extended the previous sequence by 1 and now we would need coin of 8 or less value.\n\nNow, if we get a coin 9, then there\'s no way we can extend the sequence. The sequence previously formed was upto 7 and we needed to get a coin of value less than or equal to 8 to extend the sequence.\n\n------------\n\n**We can generalize pattern** - we can extend the current consecutive sequence, if the coin we are going to choose is less than or equal to the `current sum + 1`.\n\n```\nint getMaximumConsecutive(vector<int>& coins) {\n\tsort(begin(coins), end(coins));\n\tint curSum = 0;\n\tfor(auto& coin : coins)\n\t\tif(coin <= curSum + 1) curSum += coin;\n\t\telse break;\n\n\treturn curSum + 1;\n}\n```\n\n**Time Complexity :** **`O(NlogN)`**\n**Space Complexity :** **`O(1)`**, ignoring the implicit space required by the sort algorithm\n\n------------\n------------
['C']