1798. Maximum Number of Consecutive Values You Can Make

基本上直接這題給卡死XD, 如果想不到的話應該在現場當下很難想到

我一開始是dfs, 造出所有可能後然後從0開始找, 直到做不出來的就回傳

但這樣會tle, 我當下用很多很精簡, dfs演算法還是花太長的時間了

先sort整個陣列

若coins[i] > res,

則說明當前的res, 你不管怎樣用coin都做不出來, 即可回傳

若coins[i] ≤ res

我們則可以做出 0 … res — 1的所有可能

這邊我花了好一段時間去理解, 為什麼

這需要一點腦力XD

現在res = 4, 而coins[i] = 2
代表, 從 0...3 , 的組合中,  每個都可以再加一個2, 所以我們就變相可以做出0...5的可能, 而res就會提升至6

挖靠, 太鬼了吧, 當下反而會考慮很多類似如果組合被用過什麼的, 但就如上面所言, 無須多想是否組合會不可行

時間複雜度也就是sort coins O(nlogn)

class Solution {
public:
    int getMaximumConsecutive(vector<int>& coins) {
        sort(coins.begin(), coins.end());
        int res = 1;
        for(auto a: coins){
            if(a > res){
                break;
            }
            res += a;
        }
        return res;
    }
};