「JoyOI1049」最长不下降子序列

2013年12月1日4,4501

题目描述

有由n个不相同的整数组成的数列，记为:a₁、a₂、……、a_n，例如3，18，7，14，10，12，23，41，16，24。若存在i₁<i₂<i₃< … < i_e 且有a(i₁)<＝a(i₂)<＝ … <＝a(i_e)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。

输入

第一行为n，表示n个数第二行n个数

输出

最长不下降子序列的长度

样例输入

3 1 2 3

样例输出

提示

N小于5000 for each num < =maxint

代码

#include<iostream> 
using namespace std; 
int main() 
{ 
    int n,a[5001]={0},h[5001]={0},max,best=0;; 
    cin>>n; 
    for(int i=1;i<=n;i++) 
        cin>>h[i]; 
    a[1]=1; 
    for(int i=2;i<=n;i++) 
        { 
            max=1; 
            for(int j=1;j<=i-1;j++) 
                if(h[j]<=h[i]) 
                    if(a[j]>=max) max=a[j]+1; 
                    a[i]=max; 
        } 
    for(int i=1;i<=n;i++) 
        if(a[i]>best) best=a[i]; 
    cout<<best<<endl;  
}