longest ordered subsequence2.cpp

本问题是计算最长有序子序列的一个动态规划算法,效率为31MS.

#include <stdio.h> 
struct node{
       int x,y;
       }a[1000];
int main() 
{  
    int n,i,j,max; 
    scanf("%d",&n); 
   for(i=0;i<n;i++) 
   {
                    scanf("%d",&a[i].x); 
                    a[i].y=1; 
   } 
     for(i=0;i<n-1;i++) 
     for(j=i+1;j<n;j++) 
     if(a[j].x>=a[i].x && a[j].y<=a[i].y) 
     a[j].y++; 
     max=a[0].y;
     for(i=1;i<n;i++) 
     if(a[i].y>max) 
     max=a[i].y; 
     printf("%d",max); 
     return 0;
}