题解 | 合唱队形

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int index = 0;
        int[] nums = new int[n];
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            nums[index] = in.nextInt();
            index++;
        }
        // 排列为合唱队形
        // i位置最高，左边连续递增，右边连续递减
        // 找左边最大上升序列，找右边最大递减序列
	  
        int[] dp = new int[n];
        Arrays.fill(dp,0);
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
		  // 注意边界条件，试错了很多次
            int[] left = Arrays.copyOfRange(nums,0,i+1);
            int[] right = Arrays.copyOfRange(nums,i,n);
            // if(i == n - 1){
            //     dp[i] = (i - up(left))
            // }
            int lenLeft = i + 1 - up(left);
            int lenRight = n - i - down(right);
            dp[i] = (i + 1 - up(left)) + (n - i - down(right));
            res = Math.min(res,dp[i]);
            
        }
        // System.out.println(up(Arrays.copyOfRange(nums,0,4)));
        // System.out.println(up(Arrays.copyOfRange(nums,3,4)));

        System.out.println(res);
        
    }

    public static int up(int[] nums){
        // 求最大上升序列的长度
        int count = 1;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            count = Math.max(count, dp[i]);
        }
        return count;
    }

    public static int down(int[] nums){
        // 求最大上升序列的长度
        int count = 1;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] < nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            count = Math.max(count, dp[i]);
        }
        return count;
    }

    public static void print(int[] nums){
        for(int x : nums){
            System.out.println(x);
        }
    }
}