题解 | #在字符串中找出连续最长的数字串#

参考 力扣300题，利用贪心+二分查找找出以每个元素结尾的最长上升子序列、以每个元素开始的最长下降子序列。 将数组反转后查找最长上升子序列，即为最长下降子序列。 但和力扣300 不同的是，除了用dp数组记录每个长度的子序列末尾的最小值，还需要记录以每个元素结尾的最长上升子序列长度

from typing import List

def findLis(nums: List[int]) -> List[int]:
    """查找数组 nums 中每个以每个元素结尾的最长上升子序列长度。
    返回数组 results，其中每个元素 results[i] 值表示以 nums[i] 结尾的最大上升子序列的长度
    """
    results = [1]
    # dp[i] 表示遍历过程中长度为 i+1 的上升子序列的最后一个数的最小值
    dp = [nums[0]]
    for i in range(1, len(nums)):
        if nums[i] > dp[-1]:
            dp.append(nums[i])
        else:
            # 用二分查找，找到 dp 中第一个大于等于 nums[i] 的元素，并用 nums[i]替换掉它
            left = 0
            right = len(dp) - 1
            while left < right:
                mid = (left + right) // 2
                if nums[i] > dp[mid]:
                    left = mid + 1
                elif nums[i] < dp[mid]:
                    right = mid
                else:
                    left = mid
                    break
            dp[left] = nums[i]
        results.append(len(dp))
        
    return results



while True:
    try:
        l = int(input())
        nums = [int(i) for i in input().split(' ')]
#         print(nums)
        results1 = findLis(nums)
#         print(results1)
        nums.reverse()
        results2 = findLis(nums)
#         print(results2)
        
        maxCount = 0
        for i in range(len(results1)):
            maxCount = max(maxCount, results1[i]+results2[len(results1)-1-i])
        print(len(nums) - maxCount + 1)
    except EOFError:
        break