HJ24 合唱队
解析：这道题可以参考该视频的思路，使用left和right数组记录元素i左边递增的元素个数和右边递减元素的个数。left和right数组的值由前面的状态推出，如果i比前面的某一元素ii大，则left[i] = max(left[i], left[ii] + 1),最后只需把left和right加起来减一即是合唱队剩余人数。
注意：这道题在牛客上用python运行显示超时，用Java可以通过。
# python
n = int(input())
list = []
left = [1] * n # left[i]表示0~i位置上最长的递增子序列的长度
right = [1] * n # # right[i]表示i~n-1位置上最长的递减子序列的长度
res = 0
list = [int(n) for n in input().split(' ')]
for i in range(n):
for ii in range(i):
if list[i] > list[ii]:
left[i] = max(left[i], left[ii] + 1) # 动态规划，取最大值
for j in range(n - 1, -1, -1):
for jj in range(n - 1, j, -1):
if list[j] > list[jj]:
right[j] = max(right[j], right[jj] + 1)
for i in range(n):
res = max(res, left[i] + right[i]) # left[i] + right[i]表示组成合唱队人数，最高值多加了一次
print(n - res + 1)
// Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n = sc.nextInt();
int[] list = new int[n];
for (int i = 0; i < n; i++) {
list[i] = sc.nextInt();
}
int[] left = new int[n];
int[] right = new int[n];
for (int i = 0; i < n; i++) {
left[i] = 1;
for (int ii = 0; ii < i; ii++) {
if (list[i] > list[ii]) {
left[i] = Math.max(left[i], left[ii] + 1);
}
}
}
for (int j = n - 1; j >= 0; j--) {
right[j] = 1;
for (int jj = n - 1; jj > j; jj--) {
if (list[j] > list[jj]) {
right[j] = Math.max(right[j], right[jj] + 1);
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
res = Math.max(res, left[i] + right[i]);
}
System.out.println(n - res + 1);
}
}
}
