第二题 Python版 import sys if __name__ == "__main__": def lagr(l,num): dp = [1]*l for i in range(l): for j in range(i): if num[j] < num[i] and dp[i]<dp[j]+1: dp[i] = dp[j] +1 s = max(dp) return l-s def small(l,num): dp = [1]*l for i in range(l): for j in range(i): if num[j] > num[i] and dp[i]<dp[j]+1: dp[i] = dp[j] +1 s = max(dp) return l-s n = int(sys.stdin.readline().strip()) for i in range(n): l = n = int(sys.stdin.readline().strip()) line = sys.stdin.readline().strip() nums = list(map(int, line.split())) ans = min(lagr(l,nums),small(l,nums)) print(ans)
t = int(input().strip()) def solu(num): n = len(num) ans = [num[0]] for i in range(1, n): if num[i] > ans[-1]: ans.append(num[i]) else: l, r = 0, len(ans) while l <= r: mid = (l + r) // 2 if num[i] > ans[mid]: l = mid + 1 elif num[i] < ans[mid]: r = mid - 1 else: r = mid -1 break ans[r + 1] = num[i] return len(ans) for _ in range(t): n = int(input().strip()) nums = list(map(int, input().strip().split(' &(5528)#39;))) res = solu(nums) res = max(res, solu(nums[::-1])) print(len(nums) - res) 第二题 python写法