最长上升子序列（代码实现）

经典问题，不在赘述

#include <cstdio>
#include <cstring>
const int maxn = 10000;
//用maxlen[i]表示a[1], a[2],..., a[k]中最长上升子序列的长度
//那么状态转移方程为
//maxlen[1] = 1
//maxlen[i] = 1 + MAX{maxlen[j], 其中1 <= j < i, a[j] < a[i]}, (1 < i <= n)
void init(int n, int *a, int *maxlen)
{
    memset(maxlen, 0, sizeof(maxlen));
 maxlen[1] = 1;
 for (int i = 2; i <= n; i++) {
  int tem = 0;
  for (int j = 1; j < i; j++) {
   if (a[j] < a[i] && tem < maxlen[j])
    tem = maxlen[j];
  }
  maxlen[i] = tem + 1;
 }

 return;
}
//寻找maxlen[maxn]中的最大值
int solve(int n, int *a, int *maxlen)
{
 int ans = 0;
 for (int i = 1; i <= n; i++)
  if (ans < maxlen[i])
   ans = maxlen[i];
 return ans;
}

int main()
{
    freopen("data.in", "r", stdin);
 int n;
 while (scanf("%d", &n) == 1) {
  int a[maxn], maxlen[maxn];
  for (int i = 1; i <= n; i++)
   scanf("%d", a + i);

  init(n, a, maxlen);
  int ans = solve(n, a, maxlen);

  printf("%d\n", ans);
 }

 return 0;
}