题解 | 合唱队

import sys

# 最长上升子序列，容易超时，所有操作放一个函数尽可能循环做完处理
def f(n,nums):
    nums_re=nums[::-1]
    dp=[1]*n
    dpb=[1]*n
    ans=1
    for i in range(n):
        for j in range(i):
            if nums[j]<nums[i]:
                dp[i]=max(dp[i],dp[j]+1)
            if nums_re[j]<nums_re[i]:
                dpb[i]=max(dpb[i],dpb[j]+1)
    for i in range(n):
       ans=max(ans,dp[i]+dpb[-i-1]-1) 
    return n-ans

n=int(sys.stdin.readline().strip())
nums=list(map(int,sys.stdin.readline().strip().split()))
print(f(n,nums))