样例过了但才40，求调

cancan1030 @ 2024-02-06 09:44:21

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N],b[N],cnt; 
int main(){
    int n;
    cin>>n;
    memset(b,N,sizeof(b));
    b[0]=b[1]=-N;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,j=0;i<=n;i++){
        if(a[i]<b[j]&&a[i]>b[j-1]){
            b[j]=a[i];
//          for(int k=1;k<=n;k++){
//              cout<<b[k]<<" ";
//          }
//          cout<<endl;
        }
        else if(a[i]>b[j]){
//          cout<<a[i+1]<<" ";
            b[++j]=a[i];
//          for(int k=1;k<=n;k++){
//              cout<<b[k]<<" ";
//          }
//          cout<<endl;
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
} 

by Michelle01 @ 2024-02-06 13:37:06

@cancan1030 在吗

by Michelle01 @ 2024-02-06 13:47:39

@cancan1030 不好意思哈，我刚刚的回答有一些错误。就是你知道上升子序列是什么意思吗。给你举个例子 1.2.3.5.7.9.10.11.12.13.14 这十一个数对吧，它的最长上升子序列是 9.10.11.12.13.14 。但是如果你用你的程序来运行下你试试，你的程序输出的答案是11。这是不对的。最长上升子序列它们之间的差都为1 也都是逐渐递增的。

by cancan1030 @ 2024-02-06 22:12:04

@Michelle01 可是AC代码运行下来的结果也是11啊……

by cancan1030 @ 2024-02-07 10:43:33

@Michelle01 在吗？

by cancan1030 @ 2024-02-07 10:53:34

@Michelle01 最长上升子序列定义： 最长上升子序列（Longest  Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。假设我们有一个序列 bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N，但必须按照从前到后的顺序。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，我们就会得到一些上升的子序列，如(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等，而这些子序列中最长的（如子序列(1, 3, 5, 8) ），它的长度为4，因此该序列的最长上升子序列长度为4。

by cancan1030 @ 2024-02-07 10:56:49

@Michelle01 所以最长上升子序列每个元素之间的差似乎并不一定都为一吧……

by Michelle01 @ 2024-02-07 17:21:45

@cancan1030 在的，我确实能力不太够，给你指导的内容都不对，实在不好意思。但是你这一题不适合用二分栈， 二分栈适合用在你去加入一些区间，入栈和出栈。可是这一题你要是非要套到栈里去用的话。。。。就会出现问题的。毕竟这一题的弹栈操作不太好写。看你怎么写了，我太菜了

by cancan1030 @ 2024-02-08 10:34:56

@Michelle01 嗯嗯