题解 | #合唱队#

标题

// 把题目转化为找最多的队伍 最后一减即可
// 一步一步仔细分析 用笨方法或者计算机的思路去分析？
// 要找全部人的最多队伍 可以一个人一个人找啊
// 当这个人最高时 左边一定比他矮 找左边所有比他矮的最长战队
// 当这个人最高时 右边一定比他矮 找右边所有比他矮的最长战队
// 这个人的符合条件的左右人数的和便是这个人的结果
// 得到所有人的结果 取最大值即为最终结果
//
// 如果我们遍历每个人，得到每个人的左右，那么后一个不能利用前一个人的信息，这样就不好了。
// 可以想到的是 当直接计算每个人的左边最长战队时 后一个人可以利用前一个人的
// 所以我们的思路是有两个函数 leftMax(arr[]) rightMax(arr[])

import java.util.*;



public class Main{
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextLine()){
            Integer N =Integer.parseInt(sc.nextLine());
            String[] strs = sc.nextLine().split(" ");
            int[] arr = new int[strs.length];
            for(int i =0;i<arr.length;i++){
                arr[i] = Integer.parseInt(strs[i]);
//                  System.out.print(arr[i]);
            }

            int[] leftRes = leftMax(arr);
            int[] rightRes = rightMax(arr);
            int max = 0;
            for(int i =0;i<arr.length;i++){
//                 System.out.println(leftRes[i]+"  "+ rightRes[i]);
                max = Math.max(max,leftRes[i]+rightRes[i]+1);
            }
            System.out.println(arr.length - max);
        }
    }
    public static int[] leftMax(int[] arr){
        int[] leftRes = new int[arr.length];
        for(int i =1; i<arr.length;i++){
            for(int j = 0;j<i;j++){
                if(arr[j]<arr[i]){
                    leftRes[i] = Math.max(leftRes[j]+1,leftRes[i]);
                }
            }
        }
        return leftRes;        
    }

    public static int[] rightMax(int[] arr){
        int[] leftRes = new int[arr.length];
        for(int i =arr.length-2; i>=0;i--){
            for(int j = arr.length-1;j>i;j--){
                if(arr[j]<arr[i]){
                    leftRes[i] = Math.max(leftRes[j]+1,leftRes[i]);
                }
            }
        }
        return leftRes; 
    }
}