题解 | #合唱队#

思路

以每个位置为中心，找它左边的递增序列长度的最大值，和它右边的递减序列长度的最大值。二者求和再加上本元素，就是合唱队的长度。

如何找左边递增序列长度的最大值呢？

设置一个数组left，初始化为0，从第2个元素开始遍历，以当前元素为中心点，向左遍历，如果左边的元素比中心点小，就进行三角不等式判断，保存原本长度和左边元素对应的长度+1。具体看代码吧。

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

全部代码如下

package module03;

import java.util.Scanner;

/**
 * --------------------------------------------
 * FileName:     合唱队
 * CreateBy:     IntelliJ IDEA
 * Author:       ffforest2012
 * Date:         2023-04-13
 * Description :
 * --------------------------------------------
 */
public class 合唱队 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n];
        int[] left = new int[n];// 本元素的左边递增序列 最多有多少个元素
        int[] right = new int[n];// 本元素的右边递减序列 最多有多少个元素
        for (int i = 0; i < n; i++) {
            q[i] = sc.nextInt();
        }

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

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (q[i] > q[j]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        int res = n;
        for (int i = 0; i < n; i++) {
            int sum = 1 + left[i] + right[i];
            res = Math.min(res, n - sum);
        }
        System.out.println(res);

    }
}