練習點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; }