合唱队(动态规划)

描述
计算最少出列多少位同学，使得剩下的同学排成合唱队形

N 位同学站成一排，音乐老师要请其中的 (N - K) 位同学出列，使得剩下的 K 位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 T1，T2，…，TK ， 则他们的身高满足存在 i （1<=i<=K） 使得 T1<T2<…<Ti-1Ti+1>…>TK 。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

请注意处理多组输入输出！

输入描述：
有多组用例，每组都包含两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输出描述：
最少需要几位同学出列

示例1
输入： 8
“”“”“”“”“”186 186 150 200 160 130 197 200
输出： 4
说明：
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

思路

先找左边，左边比自己小的元素作为i时，其左边保留的最大个数，最后加上自己；
再找右边，右边比自己小的元素作为i时，其右边保留的最大个数，最后加上自己；
最后得到每个元素节点 作为 i 时能保留的最大个数（其左边个数 + 右边个数）；
因为计算左变和右边时都加上了自己，有重复累加自己，所以减掉1；

（动态规划：每个子结果都依赖于上一步计算的结果）

代码：

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author gufusheng
 * @time 2021/11/3 11:25
 */
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {

            int n = scanner.nextInt();
            int [] dp = new int[n];
            for (int i = 0; i < n; i++) {
                dp[i] = scanner.nextInt();
            }
            int [] left = new int[n];
            int [] right = new int[n];

            // 左边找出最大
            for (int i = 0; i <n; i++) {
                left[i]++; // 自己就算一个
                int max = 0;
                for (int j = 0; j < i; j++) {
                    if (dp[j] < dp[i]) {
                        if (left[j] > max) {
                            max = left[j];
                        }
                    }
                }
                left[i] += max;
            }
            // 右边找出最大
            for (int i = n -1; i >= 0; i--) {
                right[i]++;
                int max = 0;
                for (int j = n - 1; j > i; j--) {
                    if (dp[j] < dp[i]) {
                        if (right[j] > max) {
                            max = right[j];
                        }
                    }
                }
                right[i] += max;
            }

            // 将左边和右边相加
            int [] max = new int[n];
            for (int i = 0; i < n; i++) {
                max[i] = left[i] + right[i] - 1; // 因为左右两边做算上了当前i自己，所以-1
            }
            int maxCount = Arrays.stream(max).max().getAsInt();
            System.out.println(n - maxCount);
        }
    }
}