P1189 30分

· · 题解

P1189 - 最长上升子序列 描述 设有整数序列A [1]，A [2]，A [3]，...，A [米]，若存在下标I1 <I2 <I3 <I ... <在，且A [I1] <A [I2 ] <A [i3] <... <A [in]，则称为序列A [1]，A [2]，A [3]，...，A [m]中有长度为n的上升子序列A [i1] ]，A [i2]，A [i3]，...，A [in]。 请编程计算指定序列的最长上升子序列长度。

输入 第一行一个正整数N（N <10001），表示序列中整数个数; 第二行是空格隔开的Ñ个整数组成的序列。

产量 一个正整数，表示输入文件中整数序列的最长上升子序列的长度。

样本输入 7

1 7 3 5 9 4 8

样本输出 4

暗示 样例说明： 序列（1,7,3,5,9,4,8​​）最长上升序列有：（1,3,5,9），（1,3,5,8），（1,3 ，4,9），他们长度为4。

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],ans;
int main(){
    cin>>n;
    //<int>
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]<a[i-1]&&a[i]>a[i-2])
        {
            a[i-1]=a[i];
            i--;
            n--;
        }
        else
        {
            continue;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            cout<<ans;
            return 0;
        }
        else
        {
            ans++;
        }
    }
    cout<<endl<<endl<<ans;
    return 0;
}