题解 | #动态规划，最长上升子序列的运用#

import java.util.* ;
public class Main{
    public static void main(String...args) {
        Scanner sc = new Scanner(System.in) ;
        while(sc.hasNextLine()) {
            int n = sc.nextInt() ;
            sc.nextLine() ;
            int[] arr = new int[n] ;
            for(int i = 0 ; i < n ; i ++) {
                arr[i] = sc.nextInt() ;
            }
            sc.nextLine() ;
            System.out.println(solu(arr)) ;
        }
    }
    public static int solu(int arr[]) {
        int[] up = maxUp(arr) ;//上升
        //将数组反转，再求最长上升子序列，再反转，就成了以每个i为开始的最长下降子序列长度
        reverse(arr) ;
        int dow[] = maxUp(arr) ;
        reverse(dow) ;//下降
        int max = -1 ;
        for(int i = 0 ; i < arr.length ; i ++) {
            //i左边和右边都满足条件的最大长度
            int temp = up[i]+dow[i] -1 ;
            if(temp > max) {
                max = temp ;
            }
        }
        //原长度减去求出来的最大长度就成了移除得到最少个数
        return arr.length - max ;
    }
    //动态规划求最长上升子序列
    public static int[] maxUp(int[] arr){
        int s = 0 ;
        int e = arr.length-1 ;
        //f1[i]表示i位置结尾的左边最长上升子序列长度
        int f[] = new int[arr.length] ;
        f[0] = 1 ;
        for(int i = 1 ; i <= e ; i ++) {
            //转移方程：f[i] = max{f[k]}+1,arr[k]<arr[i]
            int max = 0 ;
            for(int j = 0 ; j < i ; j ++) {
                if(arr[j] < arr[i]) {
                    if(f[j] > max) {
                        max = f[j] ;
                    }                    
                }
        }
            f[i] = max + 1 ;
        }
       return f ;
   
    }
    public static void reverse(int arr[]) {
        int i = 0 ; 
        int j = arr.length-1 ;
        while(i < j) {
            int t = arr[j] ;
            arr[j] = arr[i] ;
            arr[i] = t ;
            i++;
            j-- ;
        }
    }
}