本文共 1741 字，大约阅读时间需要 5 分钟。

题目描述

解法一：动态规划

• 时间复杂度：O(n ^ 2)


• 空间复杂度：O(n)


• 状态定义：dp[i]表示nums[0…i]的最长的子序列，且必须nums[i]被选中且在最后


• 状态转移：依次遍历dp[0…i-1]，如果nums[j] < nums[i]，那么dp[i] = dp[j] + 1，并且dp[i]取最大的那一个。

class Solution {
   public:    int lengthOfLIS(vector<int>& nums) {
           int n = nums.size();        vector<int> dp(nums.size());        int res = 1;        dp[0] = 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);                }            }            res = max(dp[i],res);        }        return res;    }};

解法二：动态规划+贪心+二分查找

参考大佬的题解：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

• 时间复杂度：O(nlogn)


• 空间复杂度：O(n)

//动态规划+贪心+二分class Solution {
   public:    int lengthOfLIS(vector<int>& nums) {
           vector<int> dp(1);     //dp[i]表示长度为i+1的子序列中最后一个元素最小的那个值（dp是递增的）        dp[0] = nums[0];       //初始化，长度为1的子序列默认先设置为第一个元素        for(int i = 1;i<nums.size();++i){
               int num = nums[i]; //当前遍历到的元素            if(num > dp.back()){
                   dp.push_back(num);  //如果当前遍历到的num比dp的最后一个元素还要大            }else{
                   //二分查找，找到dp中第一个大于等于num的                int L = 0,R = dp.size() - 1;                while(L < R){
                       int mid = (L + R) >> 1;                     if(dp[mid] < num){
                           L = mid + 1;                    }else{
                           R = mid;                    }                }                //循环结束之后，L=R,L和R就是找到的第一个大于等于num的下标                dp[L] = num; //如果dp[L]==num，那么保持不变；dp[L]>num，可以让他变小。                            }        }        return dp.size();    }};