AcWing 896. 最长上升子序列 II

2023-10-27 16:27:16

1、与原始版本区别

原始版本：\(1≤N≤1000\)，本题要求：\(1≤N≤100000\)

\(N\)的数据范围大了\(100\)倍,原始版本的题的时间复杂度是\(O(N^2)\),\(1000^2=1000000\)，是\(1e6\)，是可以\(1\)秒过的，但如果是\(100000^2=10000000000\),是\(1e10\)，超时，需要要优化~

2、优化的思路

要想优化原始的算法，肯定要找到上个式子运算的冗余，然后避免冗余，才能优化。有什么样的冗余呢？

以上图中的每3位2为例，它可以接在数字3后面，也可以接在数字1后面，都可以获取到最长上升子序列值2。其实，这里就是可以优化的地方，因为如果1和3的效果相同，1还小，可利用的机会就会更高，没理由不培养它，没必要还去找3，这样就会节约时间，这是一个贪心的思想。

如果我们把这个规律利用下来，就可以达到优化的目标了：把最长子序列长度一样的数字，用一个数组保存下来，一路循环，一路维护最小的数值在里面，每次出现新的数字时，我们就去到这个里面去找就OK。如果还不理解，就看一下下面的栗子吧，保证秒懂：

举个栗子

假设存在一个数组d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为n=5。

下面一步一步试着找出它。

我们定义一个数组q，然后令 i = 1 to 9 逐个考察数组d。此外，我们用一个变量len来记录现在最长算到多少了

首先，把d[1]有序地放到q里，令q[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1

然后，把d[2]有序地放到B里，令q[1] =1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1

接着，d[3] = 5，d[3]>q[1]，所以令q[1+1]=q[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候q[1..2] = 1, 5，Len＝2

再来，d[4] = 3，它正好值在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候q[1..2] = 1, 3，Len = 2

继续，d[5] = 6，它在3后面，因为q[2] = 3, 而6在3后面，于是很容易可以推知q[3] = 6, 这时q[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。

第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到q[3] = 4。q[1..3] = 1, 3, 4， Len继续等于3

第7个, d[7] = 8，它很大，比4大，嗯。于是q[4] = 8。Len变成4了

第8个, d[8] = 9，得到q[5] = 9，嗯。Len继续增大，到5了。

最后一个, d[9] = 7，它在q[3] = 4和q[4] = 8之间，所以我们知道，最新的q[4] =7，q[1..5] = 1, 3, 4, 7, 9，Len = 5。

于是我们知道了LIS的长度为5。

!!!!! 注意。这个1,3,4,7,9不是LIS，它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字 8 和 9，那么就可以把8更新到d[5], 9更新到d[6]，得出LIS的长度为6。

然后应该发现一件事情了：在q中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用二分查找，将每一个数字的插入时间优化到O(logN)~~~~~于是算法的时间复杂度就降低到了O(NlogN)～！

C++ 代码

#include <iostream>

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; //最长上升子序列的长度,最开始是0,q里的元素个数

    //枚举每个数
    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;
        }
        // 更新一下最大值[可能在某两个数中间，返回的是r+1]
        len = max(len, r + 1);
        //更新,可能是新的位置，也可能是修改了旧的数据
        q[r + 1] = a[i];
    }
    //返回len
    printf("%d\n", len);
    
    return 0;
}

网友的实现代码，很棒

#include <iostream>

using namespace std;
const int N = 100010;

int n;
int s[N];   //存储每个数
int q[N];   //所有不同长度情况下，上升子序列结尾数字的最小值
int pos[N]; 

int main() {
    cin>>n;
    for (int i = 0; i < n; i++) cin>>s[i];
    q[0] = s[0]; //首个就是原数组中的首个数据
    
    int len = 0;
    for(int i = 1; i < N; i++){
        if(s[i] > q[len])    //如果能直接接在后面
            q[++len] = s[i]; 
        else {
            //https://blog.csdn.net/niushuai666/article/details/6734403
            //前闭后开区间进行二分查找
            //int p=lower_bound(q, q+len, s[i])-q;
            //q[p]=s[i];
            *lower_bound(q, q+len, s[i])=s[i];//用二分法找dp中第一个大于s[i]的数，要是不会用循环也是可以的。
        }
    }
    //返回len
    printf("%d\n", ++len);
    
    return 0;
}

怎么求出LIS的路径呢？

注意，q数组中存的并不一定是正确LIS，但是不影响求LIS长度。其实这个算法记录路径也并不复杂，我们在遍历目标数组时，数组里的每一个数都是有机会进入q数组的，所以我们构造一个pos数组，在每个数进入q时，记录该数在q的位置，表示以该数结尾的LIS长度，原数组遍历结束后，从右往左寻找pos中的最大值，最终就会得到一个倒着的LIS序列，代码也比较好理解

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 100010;
int n = 7;

int q[N], pos[N], pre[N], len = 0, maxi;
int a[N] = {2, 1, 5, 3, 6, 4, 8, 9, 7};


void print() {
    int lis[N];
    for (int i = len - 1; i >= 0; i--) { //倒序放入lis序列，从大到小反向遍历
        lis[i] = a[maxi];
        maxi = pre[maxi];
    }
    for (int i = 0; i < len; i++)
        cout << lis[i] << " ";
    cout << endl;
}

//若想得到最长递增子序列，同样可以使用数组lastidx和pre，用来标识至此为止该长度的LIS的最后一个数的下标和当前数字的来源
/*
注意dp数组并不一定是LIS，而是对应长度的LIS的最后一位。而注意到dp数组往往是有序的，所以数组元素只有替换而没有挪动，故每次插入只要用二分查找即可。因此复杂度为O(N logN)
若想得到最长递增子序列，同样可以使用数组pos和pre，用来标识至此为止该长度的LIS的最后一个数的下标和当前数字的来源
*/
int main() {
    //为什么要这样设置初始值
    memset(q, 0x3f, sizeof q); //正无穷
    q[0] = -INF;                     //第一个设置为负无穷,这样设置后，第一个进来的，就必定是在0后面，出现在1的位置上。

    //遍历每一个数据
    for (int i = 0; i < n; i++) {
        int p = lower_bound(q, q + n, a[i]) - q; //二分查找a[i]

        //找到了合适的位置
        q[p] = a[i];         //每个原数组中的元素(值)  ， 记录到dp数组中

        //上面记录的是第i个元素的值，这里记录是第i个元素的索引
        pos[p] = i;          //该长度的LIS的最后一个数的下标

        //前驱，第i个元素从哪个索引走到这里
        pre[i] = pos[p - 1]; //当前数字的来源（LIS中的前一位，即pos[长度-1]）

        if (p >= len) {
            len = p;  //记录最大的长度
            maxi = i; //记录最大长度时的下标
        }
    }
    cout << "最长公共子串长度：" << len << endl;

    //输出路径(下面用一个普通数组通过一次反向赋值+正向遍历就可以将递归关系的数据输出出来)
    print();
    return 0;
}

码农公寓