P1091 合唱队形

为了保证中间的左边的尽可能多，右边的也尽可能多，所以选择dp[i] + dp2[i]总和 dp_all[ i ] 最大的【dp[i]+dp2[i] 加多一个自己】

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        int N = sc.nextInt();
        int arr[] = new int [N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = sc.nextInt();
        }

        int dp_all[] = new int[N];
        int dp[] = new int[N];
        int dp2[] = new int[N];
        for(int i = 0; i < N; i++){  //求最长上升子序列
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }
        }
        for(int i = N - 1; i >= 0; i--){  //从后往前求最长上升子序列
            dp2[i] = 1;
            for(int j = N - 1; j > i; j--){ //用max函数就超时
                if(arr[j] < arr[i] && dp2[i] < dp2[j] + 1)
                    dp2[i] = dp2[j] + 1;
            }
        }
        int MAX = -1;
        for(int i = 0; i < N; i++){
            dp_all[i] = dp[i] + dp2[i];
            MAX = Math.max(MAX, dp_all[i]);
    }
        System.out.println(N-MAX+1);
}
}