不知道哪一天的
看hint 我连LIS都不知道==
查了才知道
用了最简单的N^2方法
能过就好
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
dp_lr = [1 for _ in range(n)]
dp_rl = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if nums[j]<nums[i]:
dp_lr[i] = max(dp_lr[i], dp_lr[j]+1)
for i in reversed(range(n)):
for j in range(n-1, i, -1):
if nums[j]<nums[i]:
dp_rl[i] = max(dp_rl[i], dp_rl[j]+1)
ans = n
for i in range(n):
if dp_rl[i]>1 and dp_lr[i]>1:
ans = min(ans, n-(dp_rl[i]+dp_lr[i]-1))
return ans