题解 | #合唱队#

使用最长上升子序列问题的解法，同时优化了一下内存

import java.util.*;
public clas***ain {
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while (sc.hasNextLine()) {
                int n = sc.nextInt();
                sc.nextLine();
                int[] a = new int[n];
                for(int i = 0; i <n; i++) {
                    a[i] = sc.nextInt();
                }
                sc.nextLine();
                //zuo
                int[] dp1 = new int[n];
                for (int i = 0; i < n; i++) {
                    dp1[i] = 1;
                    for (int j =0; j< i; j++) {
                        if (a[j] < a[i]) {
                            dp1[i]= Math.max(dp1[j] +1,dp1[i]);
                        }
                    }
                }  
                //you
                int[] dp2 = new int[n];
                for (int i = n-1; i >=0; i--) {
                    dp2[i] = 1;
                    for (int j =n-1; j > i; j--) {
                        if (a[j] < a[i]) {
                            dp2[i]= Math.max(dp2[j] +1,dp2[i]);
                        }
                    }
                }
                int res = 1;
                for(int i=0; i < n;i++) {
                    a[i] = dp1[i]+ dp2[i] - 1;
                    if (a[i] > res) {
                        res = a[i];
                    }
                }
                System.out.println(n-res);
            }
        }
}