最长子序列问题
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int n;
scanf("%d", &n);
int arr[200];
int dp[200] = {0};
int i,j;
int res = 1;
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
//初始化dp数组
for(i = 0; i < 200; i++)
{
dp[i] = 1;
}
//即是最长上升子序列问题
for(i=1; i<n; i++)
{
for(j=0; j<i; j++)
{
if(arr[j] < arr[i] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j]+1;
}
}
res = dp[i] > res ? dp[i] : res;//记录最大值
}
printf("%d\n", res);
return 0;
}