最长上升子序列-HDU 5532-Almost Sorted Array

你的名字 2022-05-15 04:58 186阅读 0赞

*  # 最长上升子序列-HDU 5532-Almost Sorted Array #

--------------------

*  ## 题目链接： ##

### [Almost Sorted Array][] ###

*  ## 基础： ##

### [(LIS)最长上升子序列-二分优化][LIS_-] ###

*  ## 思路： ##

### 题目大意： ###

给一个长度为n的序列，问去掉一个元素后能不能变成非递增或非递减序列

### 题解： ###

***两种情况，一原序列本来就是非递减或非递增序列，二去掉一个元素才变成非递增或非递减序列，其他情况都NO***

因为不能确定原序列升序多还是降序多，所以对原序列求一次最长非递减子序列(在给的传送门中有写) ，倒序后再求一次

**如果求得的子序列长度 Len>=n-1 ，符合要求**

*  ## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #define MAX_SIZE 100005
    using namespace std;
    
    //int a[MAX_SIZE];
    int n;
    int LIS(int a[])
    {
        int Cnt=0;
        int Array[n+1];
        Array[0]=a[0];
        for(int i=1;i<n;i++)
        {
            if(a[i]>=Array[Cnt])
                Array[++Cnt]=a[i];
            else
            {
                int Index=upper_bound(Array,Array+Cnt+1,a[i])-Array;
                Array[Index]=a[i];
            }
        }
        return Cnt+1;
    }
    int main()
    {
        int T;
        int a[MAX_SIZE],b[MAX_SIZE];
        cin>>T;
        while(T--)
        {
            cin>>n;
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                b[n-i-1]=a[i];
            }
            int Len1=LIS(a);
            int Len2=LIS(b);
            if(Len1>=n-1||Len2>=n-1)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        return 0;
    }

[Almost Sorted Array]: http://acm.hdu.edu.cn/showproblem.php?pid=5532
[LIS_-]: https://blog.csdn.net/SZU_Crayon/article/details/82025727