传送门：https://www.luogu.com.cn/problem/P1091 这道题的话主要是一道求最长子序列的问题，但是是从正序和倒序开始求的，对于正序列的最长子序列可以看看LeetCode上的300号问题。求最长子序列当然是用dp呢具体的看下面的代码：
import java.util.Arrays; import java.util.Scanner; /** * @author 小黎 * @date 2020/10/19 16:58 * @description 对于这道义来说的话，从中间i开始找到一个前面的最长上升子序列，找到一个后面的最长下降子序列 * 在把初始的长度减去拼接过后的长度就是答案“最少需要几位同学出列” */ public class P1091 { public static void main(String[] args) { Scanner input = new Scanner(System.in); //n个同学 int n = input.nextInt(); int [] array = new int[n]; //输入身高 for (int i=0;i<array.length;i++){ array[i] = input.nextInt(); } int [] dp1 = new int[array.length]; int [] dp2 = new int[array.length]; Arrays.fill(dp1,1); Arrays.fill(dp2,1); //获取头部最长上升，这儿可以debug看看哦， for (int i=1;i<array.length;i++){ for (int j=0;j<i;j++){ if (array[i]>array[j]){ dp1[i] = Math.max(dp1[i],dp1[j]+1); } } } //获取尾部上升 for (int i=array.length-2;i>=0;i--){ for (int j=array.length-1;j>i;j--){ if (array[i] > array[j]){ dp2[i] = Math.max(dp2[i],dp2[j]+1); } } } //遍历找到最大的值 int ans = 0; for (int i =0;i<n;i++){ ans = Math.max(dp1[i]+dp2[i]-1,ans); } System.out.println(n-ans); } }emmm，虽然能过，但是复杂度确实O（n*n）的，具体的优化方法还没有找打。。。
