当前位置：编程学习 > C/C++ >>

九度教程第97题

C语言源码：
[cpp]  
#include<stdio.h>  
int max1[101],max2[101];  
int main()  
{  
    int i,j,n,num,a[101];  
    while(scanf("%d",&n)!=EOF)  
    {  
        for(i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        max1[1]=1;  
        for(i=2;i<=n;i++)  
        {  
            max1[i]=1;  
            for(j=1;j<i;j++)  
            {  
                if((a[j]<a[i])&&(max1[j]+1>max1[i]))  
                    max1[i]=max1[j]+1;  
            }  
        }  
        max2[n]=1;  
        for(i=n-1;i>=1;i--)  
        {  
            max2[i]=1;  
            for(j=n;j>i;j--)  
            {  
                if((a[i]>a[j])&&(max2[i]<max2[j]+1))  
                    max2[i]=max2[j]+1;  
            }  
        }  
        num=0;  
        for(i=1;i<=n;i++)  
            if(max1[i]+max2[i]>num)  
                num=max1[i]+max2[i];  
        printf("%d\n",n-num+1);  
    }  
}