Poj Solution 1836

http://poj.org/problem?id=1836

//* @author: 
import java.util.Scanner;
public class Main{
   private int n;
   private double a[];
   int b[],c[],sum[];
   
   public Main(int n,double a[]){
    this.n=n;
    this.a=a;
    b=new int[n+1];
    c=new int[n+1];
    sum=new int[n+1];
  }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      double a[]=new double[n+1];
      for(int i=1;i<=n;i++){
        a[i]=sc.nextDouble();//�±��1��ʼ
   
       }
      Main ma=new Main(n,a);
     // ma.showB();
      //ma.showC();
      System.out.println(ma.doIt());
      
  }

   private void showB(){
     for(int i=1;i<=n;i++){
        System.out.println(b[i]+"  ");
     }
    }

   private void showC(){
     for(int i=1;i<=n;i++){
        System.out.println(c[i]+"  ");
     }
   }
  
   private void lis(){//a[]��ǰi��Ԫ���У�����������еij���Ϊb[i]
    b[1] = 1;
    for (int i=2;i<=n;i++)
    {
        int max = 0;
        for (int j=1;j< i;j++)
        {
            if (a[j]< a[i] && b[j]>max)
            {
                 max = b[j];
            }
        }
        b[i] = max + 1;
    } 
  // showB();
}

private void flis()//a[]�ĴӺ���ǰ��n-i+1Ԫ���У�����������еij���Ϊc[i]
{
     c[n] = 1;
    for (int i=n-1;i>=1;i--)
    {
        int max = 0;
        
        for (int j=n;j>i;j--)
        {
            if (a[j]< a[i] && c[j]>max)
            {
                max = c[j];
            }
        }
        c[i] = max + 1;
    }
}

 

  private int doIt(){
    lis();
    flis();
    int min=n;
   for(int i=1;i<=n;i++){
      for (int j = i + 1; j <= n; j++) {//��ߵ������}��,���a[i]���������Լ��ȸߵ���
            if (a[i] == a[j]){
              if(c[i]<=c[j])
                c[i]=c[j]+1;
            }
        }

      sum[i]=n-(b[i]+c[i]-1);
      if(sum[i]< min){
           min=sum[i];
      }
   }
  return min;
 }

}