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

题目：

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]Output: 4Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]Output: 1

 

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

 

Follow up:

• Could you come up with the O(n2) solution?
• Could you improve it to O(n log(n)) time complexity?

 

思路1：

题意是找出最长的subsequence，此处字符列指可以不连续，但是不能破坏顺序。首先讨论的方法，用额外的vector<int>，长度与原数组相等，作为DP数组，假设叫dp。dp[i]表示到nums[i]为止最长的子序列，因此只要遍历dp中[0, i)，找到最大值，加1即可作为dp[i]的备选项。状态转移方程为。对于dp的初始化，所有格子都是1，因为自身可以作为子序列，最短至少为1。

 

代码1：

class Solution {

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

 

思路2：

Follow up问的是复杂度，这里看到对数级比较容易想到二分法。首先建立一个空数组res，用来储存到目前为止最长的subsequence。遍历nums，对于每个数，用lower_bound去寻找它应该在res里的位置，如果找到的是res.end()，说明当前的数字比res里面都要大，可以成为新的tail，把当前数加入res，否则的话说明当前subsequence里有比这个大的元素可以被替换。这一步其实主要是为了替换当前res里面的最后一个值，来控制之后可以加入的元素的最小值。其实它也会替换前面的值，比如例子数组[10,9,2,5,3,7,1,101,18]，当遍历到1时，res里是[2, 3, 7]，然后1会替换2，虽然这破坏了顺序，但是其实这无关紧要，我们最后关心的是res的长度，而不是内容。因此这个替换最重要的是替换最后一个位置如[9,2,3]遍历到2时，res里是[9]，此时res变成[2]，则后面的3可以被加入进res。但是又不能仅仅只检查res的最后一个数，因为这样会导致最后一位从大小上出错。比如[4,10,4,3,8,9]，那么遍历到4时，res是[4,10]，如果按照大小计算，10会被4替换，会导致错误。

 

代码2：

class Solution {

public:     int lengthOfLIS(vector<int>& nums) {         int n=nums.size();         vector<int> res;         for(auto i:nums)         {             auto itr=lower_bound(res.begin(),res.end(),i);             if(itr==res.end())                 res.push_back(i);             else                 *itr=i;         }         return res.size();     } };