思路：
動態(tài)規(guī)劃

思路解釋：
1.這里的動態(tài)規(guī)劃的應(yīng)用與以往不同，以往是直接求結(jié)果，而這里采用的方案是dp[i]代表從[0..i]中去選擇，并且一定選中i號元素。
2.之所以這樣設(shè)計是因為這樣解題的邏輯會很簡單，只需要比較一下當(dāng)前數(shù)字比之前大的數(shù)字就行，比之前大，那么長度就一定比之前的多1，依次類推。
3.要注意的是因為返回的結(jié)果是選中i后從[0..i]的最長上升子序列的長度，并不是最終結(jié)果，所以最終結(jié)果還要遍歷一遍

代碼實現(xiàn)：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();
        if(n<2)
            return n;
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<=i;j++)
                if(nums[i]>nums[j])
                    dp[i]=max(dp[j]+1,dp[i]);
        }
        
        int ret=1;
        for(int i=0;i<n;i++)
            if(dp[i]>ret)
                ret=dp[i];
        return ret;
    }
};