計算最少出列多少位同學喝滞，使得剩下的同學排成合唱隊形
說明：
N位同學站成一排专筷，音樂老師要請其中的(N-K)位同學出列强霎，使得剩下的K位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1哼转，2…，K槽华，他們的身高分別為T1壹蔓，T2，…猫态，TK佣蓉， 則他們的身高滿足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。
你的任務是亲雪，已知所有N位同學的身高勇凭，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形义辕。

總的思路是看成兩條最長子序列之和,為避免重復計算,正過來求所有,再反過來求所有,然后兩個數(shù)組逐位相加;

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-用數(shù)組維護記錄dp[i]=index前面長度為i的子序列最后一個元素index是哪個(這個最大值盡可能小)如dp[6]=9 表示長度為6的子序列最小值的腳標是9位置上的元素
        不斷刷這個表可以減少循環(huán)去刷前面所有的;(這個求最長子序列快但是求保留當前點的最長子序列還需要再回頭找)
        **/
        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++){
                    // 這里之前犯錯沒考慮等于的時候,不能讓等于情況去禍害下一個循環(huán)
                    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;

            /**
            // 思路二:直接循環(huán)求保留當前點時的最長子序列為多少,然后每一次都和前面已經(jīng)確定了的結果逐一比較,相對簡單,非常適合這題;
            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);
        }

    }
}