打卡记录

得到山形数组的最少删除次数（线性DP + 前后缀分解）

链接

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        pre, suf = [1] * n, [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    pre[i] = max(pre[i], pre[j] + 1)
                if nums[n - 1 - i] > nums[n - 1 - j]:
                    suf[n - 1 - i] = max(suf[n - 1 - i], suf[n - 1 - j] + 1)
        return min(n - (pre[i] + suf[i] - 1) for i in range(n) if pre[i] != 1 and suf[i] != 1)