九度教程第97题

题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=96

C语言源码：

#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);}}