300. 最长上升子序列

题目：给定一个整数数组，求其中最长的严格递增子序列的长度。
注意子序列和子串的区别：

• 子序列不要求连续，相对顺序不变即可
• 子串要求是连续的串
  思路：经典dp问题，定义dp[i]为以第i个数字结尾的最长上升子序列的长度，注意第i个数字被选中。

int lengthOfLIS(vector<int>& nums){
    int n = nums.size();
    if(n==0) return 0;

    int dp[n]; // dp[i]表示以第i个数字结尾的最长上升子序列的长度
    dp[0]=1;
    int res = 1;
    for(int i=1; i<n; i++){
        dp[i]=1;
        for(int j=0; j<i; j++){
            if(nums[j]<nums[i]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        if(dp[i]>res) res=dp[i];
    }
    return res;
}