【Algorithm】最长上升子序列 II

最长上升子序列 Ⅱ

这题看似是动态规划问题，但注意其数据范围。最长上升子序列动态规划做法的时间复杂度是，此题数据范围较大，必超时。

首先，求最长上升子序列的问题和它的子问题有这样的依赖关系：

上图这样就可以求得序列 3 1 2 1 8 5 6 的 LIS 长度是 4 ，把 6 接在 1 2 5 后面即可。
所以，要求串 a[0...i] 的 LIS ，就要知道：串 a[0...i-1] 中各长度的上升子序列末尾元素的最小值。 

后者可以用一个 q 数组来存储，q[i] 是所有长度为 i 的上升子序列末尾元素的最小值。这个数组是严格单调递增的（原因不赘述），所以每次只要用二分查找，在 O(logn) 的时间内就能从串 a[0...i-1] 对应的 q 数组求得串 a[0...i] 的 LIS ，完成状态转移。

q 数组的维护

接下来的难题就是如何在求得串 a[0...i] 的 LIS 后更新 q 数组，好让下一个到串 a[0...i+1] 的状态转移顺利发生。在下面的代码里面可以看到，实际上在每轮循环只需要做一件事：将本次发现的 LIS 的末尾元素赋值给 q[l+1]。为什么这么简单？有两点问题：

1. 注意这里是直接赋值，而不是求min，为什么a[i]一定不大于q[l+1]？
2.  为什么只修改q[l+1]这一项？其他项一定不需要更新吗？

画个图，就很清楚了，由于我们是二分搜索搜到的l，所以a[i]一定是严格大于 q[l]，而小于等于q[l+1]。

首先由于当前串的 LIS 长度就只有 l+1，所以 q[l+1] 后面的项肯定不会被更新。对于 q[1...l]，看这个例子就很容易明白了：

 代码一

#include 
#include 

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = a[i];
    }

    printf("%d\n", len);

    return 0;
}

代码二

#include
#include
#include

using namespace std;

int main(void) {
    int n; 
    cin >> n;
    
    vector arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];

    vector stk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
            stk.push_back(arr[i]);
        else//替换掉第一个大于或者等于这个数字的那个数
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    cout << stk.size() << endl;
    return 0;
}
/*
例 n: 7
arr : 3 1 2 1 8 5 6

stk : 3

1 比 3 小
stk : 1

2 比 1 大
stk : 1 2

1 比 2 小
stk : 1 2

8 比 2 大
stk : 1 2 8

5 比 8 小
stk : 1 2 5

6 比 5 大
stk : 1 2 5 6

stk 的长度就是最长递增子序列的长度

*/