10001.c

本问题是计算最长有序子序列的一个动态规划算法,效率为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=a[j].y+1; 
     max=a[0].y;
   for(i=1;i<n;i++) 
    if(a[i].y>max) 
      max=a[i].y; 
   printf("%d",max); 
   getchar();
   getchar();
   return 0;
}