最长上升子序列

算法描述：

给定一个序列a,求出最长的严格递增的子序列的长度。

子序列：在保证a中元素顺序不变的情况下，删除若干个元素得到的序列为子序列

一个很显然的思路：
我们考虑序列$a_1$到$a_i$：

• 当i=1时，该序列LIS长度显然为1，所以$dp_1$=1。
• 当i=2时，若$a_2$>$a_1$则，LIS长为2，即$dp_2$=2，否则，LIS仍为1，即$dp_2$=1。
• 当i=3时，在$a_1$到$a_2$之间寻找小于$a_3$的数，对于比$a_3$小的数，便可以考虑把$a_3$加入到序列中，从而LIS长度加一，即$dp_3$=1+$dp_k$。
  …以此类推
• 当i=k时，在$a_1$到$a_{k-1}$之间找出所有$a_i$<$a_k$，并取出max{$dp_i$}，则$dp_k$=max{$dp_i$}+1。

得到所有的dp后，dp中的最大值就是LIS的最大长度。

由此我们得到了LIS的递推求法：

for(int i=1;i<=n;i++)
{
    dp[i]=1;
    for(int j=1;j<i;j++)
    {
        if(a[j]<a[i])
        {
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    ans=max(ans,dp[i]);
}

分析其复杂度，显然该算法时间复杂度为O($n^2$)，空间复杂度为O(n)。

对于O($n^2$)的复杂度而言，当n>1e4的时候就非常难通过了，必须考虑更换算法。

分析上述递推算法，$dp_i$表示以$a_i$为结尾的子序列中，最长的上升子序列的长度，我们更换两者的地位，即让$dp_i$的含义修改为：长度为i的子序列，该子序列以$dp_i$为结尾。

显然$dp_i$肯定越小越好，所以$dp_i$应该为所有可能值得最小值。因为对于同样长度为i的子序列中，末尾$dp_i$越小，那么这个子序列越有可能在后面加更多的数。那么最终的答案便是最大的i。

在实际例子中，我们能够发现dp数组是单调增的，为什么呢？以下用反证法简单证明：

如果dp不是单调增，即存在i < j，但是$dp_i$>=$dp_j$，由于$dp_j$存在，即存在长度为j的以$dp_j$结尾的LIS，设该LIS为p，由于子序列上升，所以$p_i$<$p_j$，取p序列前i个作为一个长度为i的LIS，$dp_i$应该为所有可能值得最小值，所以应该有$dp_i$<=$p_i$，但是$dp_i$>$dp_j$，显然矛盾，因此dp数组单调增。

那么知道这个性质之后，问题就好办多了。
我们遍历数组a：
举例a=3,2,4,5,3,7

• 当i=1时，$dp_i$=3。{dp=3}
• 当i=2时，由于$a_i$=2小于$dp_1$=3，那么$dp_1$=2显然是更优的。{dp=2}
• 当i=3时，我们可以直接将$a_i$加入进dp后面，因为4>2。{dp=2,4}
• 当i=4时，与前面同理。{dp=2,4,5}
• 当i=5时，我们可以替换掉$dp_2$，因为3<4，存在子序列{2,3}优于子序列{2,4}。{dp=2,3,5}
  …

由此可见，我们对序列的操作实质上就是在dp中寻找比$a_i$大（或等）的数，然后进行替换。
由于dp升序，这个操作可以用二分查找实现。
而对于未找到的情况，则说明dp中所有数据都小于$a_i$，那么就可以延长dp。
最终的答案显然就是dp的长度。
于是我们就有了贪心+二分的算法：
分析其复杂度，显然时间复杂度为O(nlogn)，空间复杂度为O(n)。

Code

vector<int>dp;
for(int i=1;i<=n;i++)
{
    auto pos=lower_bound(dp.begin(),dp.end(),a[i]);
    if(pos==dp.end())dp.push_back(a[i]);
    else *pos=a[i];
}
ans=dp.size();

总结

后者算法显著优于前者（笑~）