从一道板子题了解LIS(最长上升子序列)

在理解LIS之前，需要理解什么是子序列，子序列指的是一个序列中，按照原顺序选出若干个不一定连续的元素所组成的序列，在求解LIS时，一般我们会设dp[i]表示1~i序列中以a[i]结尾的最长上升子序列的长度，状态转移方程为：

dp[i] = max(dp[j] + 1),if a[i] > a[j]//表示a[i]要插入到不同子序列后面的情况

LIS的简单模板为：

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

每次都是更新dp[i]的值，即为以i对应的数字结尾的最大上升子序列的长度，那么按照本题题意，是不是输出dp][n]即可？未必，因为所求长度为n的最长子序列不一定以n对应数字结尾，比如原数组为1,5,4,3,6,7,1,此时是以n - 1结尾，所以还是得求dp[i]的最大值，即为ans = max(ans, dp[i]),初始化ans，并且最后输出ans即可。

最后说明一下，本次写的LIS模板是朴素的形式，复杂度为O(n^2),在较小的输入量可以通过，而较大的输入量就要考虑使用二分查找对应的复杂度为O(logn)的形式来求解。我们有机会再讲，先消化下这个朴素形式。

本次LIS板子题原题链接：

https://www.lanqiao.cn/problems/2049/learning/?page=1&first_category_id=1&name=%E8%93%9D%E6%A1%A5%E5%8B%87%E5%A3%AB