def find_LIS_indices(nums):
dp = []
back = {}
for num in nums:
if not dp or dp[-1] < num:
back[num] = 0 if not dp else dp[-1]
dp.append(num)
else:
idx = bisect_left(dp, num)
dp[idx] = num
back[num] = dp[idx-1] if idx != 0 else 0
for i in range(len(dp)-1, 0, -1):
dp[i-1] = back[dp[i]]
return set(dp)
def min_actions(arr):
res = []
lis = []
left = []
s = find_LIS_indices(arr)
#print(s)
for num in arr:
if num in s:
lis.append(num)
else:
left.append(num)
left.sort()
lisi, lisn = 0, len(lis)
for i in range(len(left)):
while lisi < lisn and lis[lisi] < left[i]:
lisi += 1
res.append((left[i], lis[lisi-1]))
lis[lisi-1] = left[i]
return res
print(min_actions([1, 3, 7, 9, 5, 2])) # [(2, 5), (0, 2)]
print(min_actions([9, 7, 5, 3, 1])) # [(5, 9), (4, 7), (3, 5), (2, 3)]
print(min_actions([3, 2, 1])) # [(3, 3), (2, 2)]
print(min_actions([1, 7, 9, 2, 3, 4])) # [(6, 9), (5, 7)]
print(min_actions([1, 7, 9, 2]))
print(min_actions([1, 7, 9, 2, 5, 6, 3, 8, 10]))
Output:
[(2, 1), (5, 3)]
[(3, 1), (5, 3), (7, 5), (9, 7)]
[(2, 1), (3, 2)]
[(7, 4), (9, 7)]
[(2, 1)]
[(3, 2), (7, 6), (9, 8)]
用Rushia的改了一下 找LIS 和後面插入應該直接用數字代表就好?