HDU-1257-最少拦截系统-LIS

# include<stdio.h>
# include<string.h>
int arr[30010],lis[30010];
int list(int arr[],int n)    //arr[]存放的是待求数组
{
int i,j,max;        //max为最大递增子序列的长度
max = 0;
for(i=1;i<=n;i++)
lis[i] = 1;    //lis[i] 存放i之前的最大递增子序列的长度，初始都为1
for(i=2;i<=n;i++)    
{
for(j=1;j<i;j++)    //遍历i之前所有位置
{
if(arr[i]>=arr[j] && lis[i]<lis[j]+1)    
//arr[i]>arr[j]为递增  lis[i]<lis[j] + 1确保为当前最长递增序列
lis[i] = lis[j] + 1;
}
}
for(i=1;i<=n;i++)
if(max < lis[i])
max = lis[i];
return max;
}
int main()
{
int n,i,max;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
scanf("%d",&arr[i]);
max = list(arr,n);
printf("%d\n",max);
}
return 0;
}