合唱队形

题目要求：现有N名同学，求至少需要让多少名同学出列，使得现有的同学不需要调整就可以形成合唱队形，即中间高两边低

思路：求一个最长递增子序列和一个最长递减子序列，然后两者交集

代码：

def chorusFormation():
    # 求最长递增子序列
    def maxAscSubSeq(end):
        inde = [0 for i in range(num + 1)]
        for i in range(end + 1):
            inde[i] = 1
            for j in range(i):
                if A[j] < A[i]:
                    inde[i] = max(inde[i], inde[j] + 1)
        return inde[end]

    # 求最长递减子序列
    def maxDescSubSeq(start, end):
        inde = [0 for i in range(num + 1)]
        for i in range(end - 1, start - 1, -1):
            inde[i] = 1
            for j in range(end - 1, i, -1):
                if A[j] < A[i]:
                    inde[i] = max(inde[i], inde[j] + 1)
        return inde[start]

    while True:
        try:
            num = int(input())
            A = [int(i) for i in input().split()]
            dp = [0 for i in range(num)]
            maximal = 0
            for i in range(num):
                dp[i] = maxAscSubSeq(i) + maxDescSubSeq(i, num) - 1 # 局部最优解
                maximal = max(maximal, dp[i]) # 全局最优解
            print(num - maximal)
        except (EOFError, KeyboardInterrupt):
            break


if __name__ == '__main__':
    chorusFormation()