题解 | 合唱队

import sys
   
raw_input = []
for i,line in enumerate(sys.stdin):
    raw_input.append(line.strip())
    if i == 2:
        break

num = int(raw_input[0])
heights = [int(h) for h in raw_input[1].split(' ')]
in_lst = []
de_lst = []
length = len(heights)
for i, h in enumerate(heights):
    in_lst.append(max([in_lst[j] + 1 if heights[i] > heights[j] else 1 for j in range(i)] + [1]))
rev_heights = heights[::-1]
for i, h in enumerate(rev_heights):
    de_lst.append(max([de_lst[j] + 1 if rev_heights[i] > rev_heights[j] else 1 for j in range(i)] + [1]))

# print(in_lst)
# print(de_lst[::-1])
print(num - max([i + d for i, d in zip(in_lst, de_lst[::-1])]) + 1)

1. 使用in_lst[i]记录已heights[i]结尾的最长升序序列
2. 使用de_lst[i]记录以rev_heights[i]结尾的最长升序序列
3. in_lst与反转后的de_lst相加, 即位以该元素为峰值的合唱队序列