最大上升子序列 II

序列：可以不连续，但与原数列当中出现的先后顺序要相同；

上升子序列： 需要满足单调性 - 单调递增

算法1

(贪心+二分) O(nlogn)

时间复杂度

二分查找一个数的最小的最大值 O(logn);

一共有 n 个数进行二分 O(nlogn);

贪心

分析样例：

7
3 1 2 1 8 5 6

1.首先分析长度为1的上升子序列 —— 3 , 1

我们可以发现能接到 3 后面的数，肯定能接到1的后面，由于 3 > 1 ；

因此长度为 1 的上升子序列的结尾数最小值为 1 - min(3,1)；

2.用一个数组q[] ，来存放不同长度下上升子序列中的结尾数的最小值

q[1] : 长度为 1 的上升子序列的最小的结尾数，即为 1
q[2] : 长度为 2 的上升子序列的最小的结尾数，即为 2
q[3] : 5
q[4] : 6

因此最大上升子序列的长度为 4;（q数组中元素的个数）

规律:
随着长度的增加，结尾值一定时严格单调递增的；

也就是说，长度越长，结尾元素的最小值越大

问题：

如何找以a[i] 结尾的最大上升子序列的长度？

关键点：

对于a[i]而言，它可以接到所有比它小的末尾上；

从这一点，我们可以把a[i]接到最大的小于a[i]的结尾后面

如，比 a[i] 小的最大值为q[4]上存放的值, 即长度为4的上升子序列对应的结尾值；

说明q[4] < a[i]的，那么可以把 a[i] 接到长度为4的上升子序列上，接完之后上升子序列的长度就变成了5

这里我们可以更新长度为5的值为 a[i];

如果存在长度为5的上升子序列的结尾值，则覆盖掉原来的结尾值；

如果不存在，那么就是a[i];

为何q[5] 一定大于等于 a[i]呢？

因为q[4]是比a[i] 小的最大值，因此q[5] 肯定比a[i] 大；

二分

求最大的最小，最小的最大值时用二分

由于本题是求最小的最大值， 右向逼近

用这套板子

   while(l < r)
   {
       int mid = l + r + 1 >> 1;
       
       if(check()) l = mid;
       else r = mid - 1;
   }

C++ 代码

#include <bits/stdc++.h>
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;  
    q[0] = - 2e9;    //至于这一部分没太理解 - 后续更新
    
    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,r + 1);
        q[r + 1] = a[i];
    }
    printf("%d",len);
    return 0;
}