300. Longest Increasing Subsequence.md

300. Longest Increasing Subsequence

思路

给定一个数组，求最长递增子序列的长度。

思路一、O(n^2)

很明显是一个动态规划题，我们可以用dp[i]表示以nums[i]为结尾的最长子序列的长度。这样更新dp[i]的转移方程就为

for all j in [0, i-1]:
  if nums[i] >= nums[j]:
    dp[i] = max(dp[i], dp[j] + 1)

从转移方程可以看出有两层循环，所以时间复杂度为O(n^2)。

思路二、O(nlogn)

思路一比较好想，O(nlogn)的就不太好想了，可参考这里，讲得比较清楚。

核心思路就是：

维护一个长度可变的数组tails, tails[i]表示长度为i+1的所有递增子序列中最小的那个末尾元素，这样更新完毕后tails的长度即结果。

下面举个例子说明: 在1,3,5,2,8,4,6这个例子中，当到6时，我们一共可以有四种长度的递增子序列，在每种子序列中我们取末尾元素最小的，那么这四个序列分别是

1
1,2
1,3,4
1,3,5,6

为什么要选末尾元素最小的呢，是因为在长度一定的情况下，末尾元素最小的是未来最有可能成为最长序列的候选人。这样，每来一个新的数， 我们便按照以下规则更新这些序列：

1. 如果nums[i]比所有序列的末尾都大，说明有更长的递增序列产生，我们把最长的序列复制一遍，并加上这个nums[i]。
2. 否则，我们从前往后找，找到第一个末尾大于等于自己的那个序列，更新这个末尾。

比如这时，如果再来一个9，那就是第1种情况，更新序列为

1
1,2
1,3,4
1,3,5,6
1,3,5,6,9

如果再来一个3，那就是第2种情况，更新序列为

1
1,2
1,3,3
1,3,5,6

如果再来一个0，还是第2种情况，更新序列为

0
1,2
1,3,3
1,3,5,6

我们用一个长度可变的tails数组存储上述所有序列的末尾值（因为我们只用到了末尾值），因此tails是个递增数组，这样在第2种情况进行查找的时候就可以使用二分查找了，使复杂度降为O(nlogn)。

注意二分查找有现成的库函数：

• lower_bound(first, last, val): 返回有序数组或容器的[first, last)范围内第一个大于或等于val的元素的位置(指针或者迭代器,下同);
• upper_bound(first, last, val): 返回有序数组或容器的[first, last)范围内第一个大于val的元素的位置;

可见这里我们应该使用lower_bound找到第一个大于等于target的位置。

C++

思路一

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
        vector<int>dp(n, 1);
        
        int res = 1;
        for(int i = 1; i < n; i++){
            // j >= 0 可优化成 j >= dp[i]-1
            for(int j = i-1; j >= 0; j--)
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            
            res = max(res, dp[i]);
        }
        return res;
    }
};

思路二

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
        
        vector<int>tails;
        tails.push_back(nums[0]);
        for(int i = 1; i < n; i++){
            if(nums[i] > tails.back()) tails.push_back(nums[i]);
            else{
                tails[lower_bound(tails.begin(), tails.end(), nums[i]) - tails.begin()] = nums[i];
                // 上面这句等价于下面注释部分
                // int low = 0, high = tails.size() - 1;
                // while(low < high){
                //     int mid = low + (high - low) / 2;
                //     if(tails[mid] < nums[i]) low = mid + 1;
                //     else high = mid;
                // }
                // tails[low] = nums[i];
            }
        }
        return tails.size();
    }
};