华为机考入门python3--（24）牛客24-合唱队

分类：最长递增子序列、最长递减子序列、动态规划

知识点：

1. 从左往右求最长递增子序列（LIS）

2. 从右往左求最长递减子序列（LDS）

题目来自【牛客】

要找到能够排成合唱队形的同学数，可以使用一种叫作双层LIS（Longest Increasing Subsequence）的动态规划方法。这种方法可以找到一个数组的最长单调递增/递减子序列的长度。

具体来说，对于给定的数组，我们可以用动态规划计算出

1. 从左往右的最长递增子序列（LIS）

2. 从右往左的最长递减子序列（LDS）

然后，对于每个位置 i，我们可以计算出 LIS[i] + LDS[i] - 1，这里减去 1 是因为在这个位置上的值被加了一次。

最终，最少需要出列的同学数，即为整个数组长度减去数组中满足上述条件的最大值。

def find_lis_segment(arr):
    # 动态规划求解最长递增子序列
    n = len(arr)
    # lis[i] 表示以 arr[i] 结尾的最长递增子序列的长度
    lis = [1] * n
    # 从左往右
    for i in range(1, n):
        for j in range(0, i):
            # arr[i]对于arr[j]是递增的
            # lis[i]小于lis[j]+1
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    # 动态规划求解最长递减子序列
    lds = [1] * n
    # lds[i] 表示以 arr[i] 开始的最长递减子序列的长度。
    # 从右往左
    for i in range(n-2, -1, -1):
        for j in range(n-1, i, -1):
            # arr[i]对于arr[j]是递减的
            if arr[i] > arr[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1

    # 找出最大的lis[i] + lds[i] - 1
    max_len = 0
    for i in range(n):
        max_len = max(max_len, lis[i] + lds[i] - 1)

    # 最少需要的同学出列即为总同学数减去最大LIS长度
    return n - max_len

def main():
    n = int(input())
    heights = list(map(int, input().split()))
    result = find_lis_segment(heights)
    print(result)

if __name__ == "__main__":
    main()

求解最长递增子序列的方法可以看

https://blog.csdn.net/u013288190/article/details/135516091