合唱队

计算最少出列多少位同学，使得剩下的同学排成合唱队形
说明：
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

总的思路是看成两条最长子序列之和,为避免重复计算,正过来求所有,再反过来求所有,然后两个数组逐位相加;

import java.util.*;

public class Main{
    public static void reverse(int[] arr){
         int len = arr.length;
         for(int i=0;i<len/2;i++){
             int temp = arr[i];
             arr[i]=arr[len-1-i];
             arr[len-1-i]=temp;
         }
    }
    public static int[] maxL(int[] arr){
        int len = arr.length;
        int[] dp = new int[len+1];
        int[] result = new int[len];
        for(int i=0;i<len;i++){
            result[i]=1;
        }
        
        /**
        **思路1-用数组维护记录dp[i]=index前面长度为i的子序列最后一个元素index是哪个(这个最大值尽可能小)如dp[6]=9 表示长度为6的子序列最小值的脚标是9位置上的元素
        不断刷这个表可以减少循环去刷前面所有的;(这个求最长子序列快但是求保留当前点的最长子序列还需要再回头找)
        **/
        int max=0;
        for(int i=0;i<len;i++){

            if(i==0){
                max++;
                dp[max]=0;
                result[0]=1;
                continue;
            }
            if(arr[i]>arr[dp[max]]){
                max++;
                dp[max]=i;
            }else{
                for(int k=1;k<=max;k++){
                    // 这里之前犯错没考虑等于的时候,不能让等于情况去祸害下一个循环
                    if(arr[i]<=arr[dp[k]]){
                        dp[k]=i;
                        break;
                    } 
                }
            }
            
            int tmax=max;
            while(arr[i]!=arr[dp[tmax]]&&tmax>0){
                tmax--;
            }
            result[i]=tmax;

            /**
            // 思路二:直接循环求保留当前点时的最长子序列为多少,然后每一次都和前面已经确定了的结果逐一比较,相对简单,非常适合这题;
            for(int j=0;j<i;j++){
                if(arr[i]>arr[j]&&result[j]+1>result[i]){
                    result[i]=result[j]+1;
                }
            }
            **/

        }
        return result;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int N = scanner.nextInt();
            int[] arr = new int[N];
            for(int i=0;i<arr.length;i++){
                arr[i]=scanner.nextInt();
            }
            int[] aa = maxL(arr);
            reverse(arr);
            int[] bb = maxL(arr);
            reverse(bb);
            int result = 0;
            for(int i=0;i<aa.length;i++){
                if(aa[i]+bb[i]>result) result=aa[i]+bb[i];
            }
            System.out.println(N-result+1);
        }

    }
}