前言
應廣大同學要求，開始以OD機考題作為練習題，看看算法和數據結構掌握情況。有需要練習的可以關注下。
描述
N 位同學站成一排，音樂老師要請最少的同學出列，使得剩下的 K 位同學排成合唱隊形。
設𝐾K位同學從左到右依次編號為 1，2…，K ，他們的身高分別為𝑇1,𝑇2,…,𝑇𝐾T1?,T2?,…,TK??，若存在𝑖(1≤𝑖≤𝐾)i(1≤i≤K)?使得𝑇1<𝑇2<......<𝑇𝑖?1<𝑇𝑖T1?<T2?<......<Ti?1?<Ti??且?𝑇𝑖>𝑇𝑖+1>......>𝑇𝐾Ti?>Ti+1?>......>TK?，則稱這𝐾K名同學排成了合唱隊形。
通俗來說，能找到一個同學，他的兩邊的同學身高都依次嚴格降低的隊形就是合唱隊形。
例子：
123 124 125 123 121 是一個合唱隊形
123 123 124 122不是合唱隊形，因為前兩名同學身高相等，不符合要求
123 122 121 122不是合唱隊形，因為找不到一個同學，他的兩側同學身高遞減。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
注意：不允許改變隊列元素的先后順序?且?不要求最高同學左右人數必須相等
數據范圍：?1≤𝑛≤3000?1≤n≤3000?
輸入描述：
用例兩行數據，第一行是同學的總數 N ，第二行是 N 位同學的身高，以空格隔開
輸出描述：
最少需要幾位同學出列
輸入：
8 186 186 150 200 160 130 197 200 輸出： 4 說明：由于不允許改變隊列元素的先后順序，所以最終剩下的隊列應該為186 200 160 130或150 200 160 130
實現原理
1.使用動態規劃從左到右計算當前元素的左子序列最大長度。
2.使用動態規劃從左到右計算當前元素的右子序列最大長度。
3.所有位置的左子序列和右子序列求和，比較最大的值。
實現代碼
import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息import java.util.Scanner;public class Main {public static void main(String[] args) {// 輸入Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}//計算最長遞增序列int[] dp_left=new int[n];for(int i=0;i<n;i++){dp_left[i]=1;for(int j=0;j<i;j++){if(arr[i]>arr[j]){dp_left[i]=Math.max(dp_left[i],dp_left[j]+1);} }}//計算最長遞減序列int[] dp_right=new int[n];for(int i=n-1;i>=0;i--){dp_right[i]=1;for(int j=n-1;j>i;j--){if(arr[i]>arr[j]){dp_right[i]=Math.max(dp_right[i],dp_right[j]+1);}}}int res=0;for(int i=0;i<n;i++){res=Math.max(res,dp_left[i]+dp_right[i]-1);}System.out.println(n-res); }}}
