acm

最长上升子序列问题：（动态规划）
用递归的方法时间复杂度为：O(n*2)
#include<stdio.h>
#include<string.h>
#define max 40000+5
int tmax[max];
int value[max];
int g=0;
int d(int h,int m)
{

  if(h==m)
  {
   g++;
   return value[h]=1;
  }
  if(value[h]==0)  g++;
  value[h]=1;
 
  for(int j=h+1;j<=m;j++)
  {  
     if(tmax[h]<tmax[j]&&value[h]<(d(j,m)+1))
     {
      
         value[h]=d(j,m)+1;
       
     }
  }

  return value[h];
}
int main()
{int n;
scanf("%d",&n);
while(n>0)
{g=0;
  int m;
  scanf("%d",&m);
  memset(tmax,0,sizeof(tmax));
  memset(value,0,sizeof(value));
  for(int i=1;i<=m;i++)
  {
    scanf("%d",tmax+i);
  }
  for(int i=1;i<=m;i++)
  {
    d(i,m);
    if(g>=m) break;
  }
  int s=value[1];

  for(int i=2;i<=m;i++)
  {
     if(s<value[i]) s=value[i];
  }
  printf("%d\n",s);
  n--;
}
return 0;
}
最优算法：模拟栈操作，首先只要输入的元素大于栈顶元素，入栈，否则要找到栈中第一个比他大的数，替代它。