题解 | #合唱队#

思路：对于某个位置 i，找以它结尾的最长递增序列和以它开头的最长递减序列，它们的和（需要 - 1）就是以该位置 i 为中心，向左右递减的最长序列，合唱队的总人数减去最长序列就是需要出列的人数。

下面是求最长递增子序列的方法（参考300. 最长递增子序列）：

动态规划

用 dp[i] 表示以 i 结尾的最长递增序列，那么：

• 要么这个序列只有 i 一个，此时 dp[i] = 1。
• 要么这个序列有多个，那么 i 之前的一个 j 一定比 i 矮，它可以是小于 i 的任何一个编号。

所以有状态转移方程：

$$$

dp[i] = MAX(dp[i - j], 1), 0 <= j < i

$$$

最长递减序列的做法完全类似，根据方程可以写出代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }

            int[] maxAsc = new int[n]; // 以 i 结尾的最长递增序列
            int[] maxDesc = new int[n]; // 以 i 开始的最长递减序列
            for (int i = 0; i < n; i++) {
                maxAsc[i] = 1;
                for(int j = 0; j < i; j++) {
                    if(arr[i] > arr[j]) {
                        maxAsc[i] = Math.max(maxAsc[i], maxAsc[j] + 1);
                    }
                }
            }

            for (int i = n-1; i >= 0; i--) {
                maxDesc[i] = 1;
                for(int j = n-1; j > i; j--) {
                    if(arr[i] > arr[j]) {
                        maxDesc[i] = Math.max(maxDesc[i], maxDesc[j] + 1);
                    }
                }
            }

            int maxQueue = 0;
            for(int i = 0; i < n; i++) {
                maxQueue = Math.max(maxQueue, maxAsc[i] + maxDesc[i] - 1);
            }
            System.out.println(n - maxQueue);
        }
    }
}

贪心+二分

换一种思路：用贪心的思路就是我们总是希望递增队列的末尾身高越小越好，如果用 dp[i] 表示长度为 i 的递增队列的最后一个人的最小身高，有以下事实：

• dp 一定是有序而且递增的数组。换言之如果长度为 i 的递增队列 q，最后一人的最小身高为 h，那么长度为 i+1 的递增队列 q' 只要存在，最后一个人的最小身高 h' 必然要高于 h。因为如果 h' 低于或等于 h，那么 $ q' [i] < q'[i+1]=h' < h $，就存在了一个队列 q'[0] ~ q'[i] 它的长度和 q 相当，最后一个人的身高比最小身高 h 还要小，产生矛盾。
• dp 是这样更新的：比如我们已经有了一个正确的 dp，现在又来了一个身高为 h 的新元素，它介于 dp[i]~dp[i+1] 之间，那么我们可以更新 dp[i+1] = h，原因是 dp[i] 表示在这个新元素前方存在长度为 i 的递增队列，它的最后一个元素是 dp[i]，既然 dp[i] < h，把 h 加到这个递增队列之后，得到的长度为 i+1 的队列的最后一个元素 h 比 dp[i+1] 还小，当然应更新 dp[i+1] 的值为 h。、dp[i+2]，dp[i+3] 用不用更新？答案是不用，因为长度为 i+2, i+3 的队列的最后一个元素并没有受到 h 加入的影响，由于维护的 dp 的贪心性，以 h 结尾的最长递增序列长度就是 i+1。

由于 dp 的有序性，在更新 dp 的时候，找到 dp[i] < h < dp[i+1] 的 i 可以使用二分法以降低复杂度。

由于 dp 的贪心性，每次更新的时候的 i+1 就是以 h 结尾的最长递增序列长度。

代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            // 思路：对于某个位置 i，找以它结尾的最长递增序列
            // 和以它开头的最长递减序列
            int[] maxAsc = new int[n];
            int[] maxDesc = new int[n];

            int[] dp = new int[n];
            Arrays.fill(dp, Integer.MAX_VALUE);
            for (int i = 0; i < n; i++) {
                int left = 0, right = n;
                int h = arr[i];
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (h > dp[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                dp[right] = h;
                maxAsc[i] = right + 1;
            }

            Arrays.fill(dp, Integer.MAX_VALUE);
            for (int i = n - 1; i >= 0; i--) {
                int left = 0, right = n;
                int h = arr[i];
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (h > dp[mid]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                dp[right] = h;
                maxDesc[i] = right + 1;
            }

            int maxQueue = 0;
            for (int i = 0; i < n; i++) {
                maxQueue = Math.max(maxQueue, maxAsc[i] + maxDesc[i] - 1);
            }
            System.out.println(n - maxQueue);
        }
    }
}