最长上升子序列（LIS）问题总结

最长上升子序列 I

题目描述

给定一个长度为N的数列 $a$，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

$1 \le N \le 1000$
$0 \le a_i \le {10^9}$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路

一道很经典的动态规划问题。

• 状态表示：$f[i]$ 表示以 $a[i]$ 结尾的最长上升子序列的长度
• 状态计算：$j \in (1,2,3,.....,i -1)$，当且仅当 $a[j] > a[i]$ 时，有
  $$
  f[i] = max(f[i], f[j] + 1)
  $$
• 初始化：当数列为严格单调递减时，数列中的每个数的最长上升子序列长度就为 $1$ ，所以将$f$数组初始化为 $1$ 就行
• 最终结果：遍历一遍 $f$ 数组，取最大值

时间复杂度：$O(n^2)$

参考代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}

最长上升子序列 II

和上题一样，但是数据范围加大了，变成了 $1 \le N \le 100000$，
不用想都知道，如果用上面的解法肯定会TLE的，所以有没有什么优化方法呢？

思路

不同于上面的动态规划(DP)思想，这里想法更偏向于贪心。

这里可以用一个单调栈来存储每个最长上升子序列长度的最小末尾值，例如：$st[i]$ 表示长度为 $i$ 的最长上升子序列的末尾元素是多少。

注意一点：这个栈不是存储最终的最长上升子序列，而是：以 $st[i]$ 结尾的最长上升子序列的长度为 $i$，换句话说就是长度为 $i$ 的最长上升子序列的最小末尾值是 $st[i]$。

步骤

1. st为空，先将a[1]入栈
2. 遍历数组a
3. 若当前数大于栈顶元素，则直接入栈
4. 若当前数小于栈顶元素，则找到栈中大于等于当前数的最小值的位置，更新当前位置的值为当前数
5. 最后栈的大小就是最长上升子序列的大小

例如：

时间复杂度：$O(nlogn)$

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int a[N];
vector<int> st;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    
    st.push_back(a[1]);
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] > st.back()) st.push_back(a[i]);
        else
        {
            int l = 0, r = st.size();
            while (l < r)
            {
                int mid = l + r >> 1;
                if (st[mid] >= a[i]) r = mid;
                else l = mid + 1;
            }
            st[l] = a[i];
        }
    }
    
    printf("%d\n", st.size());
    return 0;
}