[LeetCode] 300. Longest Increasing Subsequence

練習點DP的題目 真的都忘光光惹QQ

對於每一個LIS[i]要做的是

從前方subarray找到 遞增 並且 長度最大的那個subsequence

不停bottom up往後更新後可以找到整個array裡面的Longest Increase subsequence

int lengthOfLIS(vector<int>& nums) {
    vector<int>LIS(nums.size(), 1);
    int ans = 0;
 
    for(int i = 0 ; i < nums.size(); i++) {
        for(int j = 0; j < i; j++)
            if(nums[i] > nums[j])
                LIS[i] = max(LIS[i], LIS[j]+1);
    }
    
    for(int i = 0 ; i < nums.size(); i++) {
        ans = max(ans,LIS[i]);
    }
    
    return ans;
}