不知道哪一天的
看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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730359156.A.035.html