$$\color{Red}{合唱队形-双向上升子序列}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

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

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

输入格式
输入的第一行是一个整数 N，表示同学的总数。

第二行有 N 个整数，用空格分隔，第 i 个整数 Ti 是第 i 位同学的身高(厘米)。

输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

数据范围

2 ≤ N ≤ 100

130 ≤ Ti ≤ 230

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

证明

这题明显和上一题登山没什么区别，只不过问的是当形成最大山丘人数的时候，需要出列的最少人数。直接用上题的思路，输出n - res即可

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 110, n;
    static int[] f = new int[N];
    static int[] g = new int[N];
    static int[] a = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int res = 0;
        n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        //正向上升子序列
        Arrays.fill(f, 1);
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(str[i - 1]);
            for (int j = 1; j < i; j++) {
                if (a[i] > a[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
        }
        //反向上升子序列
        Arrays.fill(g, 1);
        for (int i = n; i >= 1; i--) {
            for (int j = n; j > i; j--) {
                if (a[i] > a[j])
                    g[i] = Math.max(g[i], g[j] + 1);
            }
            res = Math.max(res, f[i] + g[i] - 1);
        }
        System.out.println(n - res);
    }
}

python

N = 110
a = [0] * N
f = [1] * N
g = [1] * N

n = int(input())
a = [0] + [int(x) for x in input().split()]
res = 0
# 正向
for i in range(1, n+1):
    for j in range(1, i):
        if a[i] > a[j]:
            f[i] = max(f[i], f[j] + 1)
    res = max(res, f[i])

#反向
for i in range(n, 0, -1):
    for j in range(n, i, -1):
        if a[i] > a[j]:
            g[i] = max(g[i], g[j] + 1)
    res = max(res, f[i] + g[i] -1)

print(n - res)