最长上升子序列（LIS）

1. 定义

给出一个序列a[1...n]，要求你求出其中最长的递增子序列的长度。

2. 简单的 O(n^2) 算法

  • 原理：
    设 dp[i] 为把下标i作为最长上升子序列结尾位置 的最大长度，则 dp[i] = max(dp[1..i]+1)，所有dp[i]初始为1.

  • 模板：

int n, num[maxn], dp[maxn];  // num[maxn]存放了序列，dp[i]表示以a[i]为结尾的最长子序列长度

int main() {
    ......
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        dp[i] = 1;
        for(int j = 1; j < i; j ++) {
            if(num[i] >= num[j]) dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

3. 最快的 O(nlgn) 算法

  • 原理：
    以非严格递增子序列为例，主要思想是 贪心 + 二分。这种方法不需要dp数组，取而代之，使用的是一个low数组。

  1. 维护一个 low数组 和 ans
    low[i]表示到当前为止，长度为i的LIS结尾元素的最小值；ans为 当前最长LIS长度
    对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长，因此该算法贪心地维护出每个长度最小的结尾元素，存放在low[i]中

  2. 维护方法
    对于每一个a[i]，如果a[i] > low[ans]，就把 a[i]接到当前最长的LIS后面，即 low[++ ans] = a[i]；否则， 用 a[i] 更新 low数组 中第一个大于 a[i] 的元素 low[j] = a[i]

  3. 举个例子
    比如1 5 6 3 4，假设当前已经遍历到下标3，则low[] = {1, 5, 6}，下一个数字3将会把5更新为3，表示到目前为止（1 5 6 3），长度为2的结尾最小的上升子序列为 1 3 。更新后下一个4才会有可能成为长度为3的上升子序列的末尾（1 3 4），这就是贪心起到的作用（总是维护最小的结尾值）。

  • 模板： 
int nums[maxn], low[maxn];  // num[maxn]存放了序列，low[i]表示长度为i的LIS结尾元素的最小值

// 贪心 + 二分 解法 O(nlogn) 
int main(){
    fill(low + 1, low + n + 1, INF);
    int ans = 0;  // low和ans搭配使用，ans就是当前维护到的最长长度
    for(int i = 1; i <= n; i ++){
        if(ans == 0 || num[i] >= low[ans]) low[++ ans] = nums[i];                            // 若为严格递增，改为 >
        else{
            int j = upper_bound(low + 1, low + n + 1, nums[i]) - low;    // 若为严格递增，改为 lower_bound
            low[j] = nums[i];
        }
    }
    cout << ans << endl;
}

4. 例题

Nowcoder 旅行青蛙

[LIS]参考博客：https://www.cnblogs.com/mengxm-lincf/archive/2011/07/12/2104745.html