时间复杂度：O(n logn)，空间复杂度：O(n)

解题思路

①动态规划

容易想到的做法为动态规划，但是时间复杂度为O(n²)，非O(n logn)，如果面试时真的忘了最优解法，用动态规划的方法也还凑合。

先讲一下我最熟悉的动态规划做法：

令dp[i]表示以nums[i]结尾的最长递增子序列长度（和最大连续子序列和问题一样，以nums[i]结尾是强制的要求）。这样对nums[i]来说就会有两种可能：

1. 如果存在nums[i]之前的元素nums[j]（j<i），使得nums[j]<nums[i]且dp[j]+1>dp[i]（即把nums[i]跟在以nums[j]结尾的LIS后面时能比当前以nums[i]结尾的LIS长度更长），那么就把nums[i]跟在以nums[j]结尾的LIS后面，形成一条更长的递增子序列（令dp[i]=dp[j]+1）。
2. 如果nums[i]之前的元素都比nums[i]大，那么nums[i]就只好自己形成一条LIS，但是长度为1，记者鸽子序列里面只有一个nums[i]。

最后以nums[i]结尾的LIS长度就是①②中能形成的最大长度。

由此可以写出状态转移方程：

dp[i]=max{1,dp[j]+1}(j=1,2,...,i-1&&A[j]<A[i])

上面的状态转移方程中隐含了边界：dp[i]=1（1≤i≤n）。显然dp[i]只与小于i的j有关，因此只要让i从小到大遍历即可求出整个dp数组。由于dp[i]表示的是以A[i]结尾的LIS长度，因此从整个dp数组中找出最大的那个才是要寻求的整个序列的LIS长度，整体复杂度为O(n²)。

②贪心+二分查找

该方法为最优解法，流程如下：

令dp数组保存目前最长的递增子序列，遍历数组时，如果遇到nums[i]比dp最后一个元素还大的情况，那么就让nums[i]加入到dp中，增加递增子序列长度，否则就二分查找dp数组，找到一个比nums[i]大且最接近的元素的下标，将其替换为nums[i]。这样做是为了能让改递增子序列容纳更多的元素，符合贪心法的特点。

至于为什么dp数组有序可参考官方题解的证明，此处不赘述。

AC代码

import "sort"//引入sort包
func lengthOfLIS(nums []int) int {
    dp:=[]int{nums[0]}//dp数组保存当前最长递增子序列元素
    for i:=1;i<len(nums);i++{
        //比递增子序列元素的最大一个元素还大
        if nums[i]>dp[len(dp)-1]{
            dp=append(dp,nums[i])//让其加入到子序列中
        }else{
            j:=sort.SearchInts(dp,nums[i])//二分查找dp数组找到贪心法替换的下标
            dp[j]=nums[i]//替换
        }
    }
    return len(dp)//dp数组的长度是最终答案
}

感悟

原先一直以为动态规划的解法是最优解法，今天才学习到原来还可以用贪心法搭配二分查找用O(n logn)的复杂度解决LIS问题，收获颇丰！