输出两行,第一行包括一个正整数n(n<=100000),代表数组长度。第二行包括n个整数,代表数组arr 。
输出一行。代表你求出的最长的递增子序列。
9 2 1 5 3 6 4 8 9 7
1 3 4 8 9
5 1 2 8 6 4
1 2 4
其最长递增子序列有3个,(1,2,8)、(1,2,6)、(1,2,4)其中第三个字典序最小,故答案为(1,2,4)
时间复杂度,空间复杂度。
def solution(nums): stack = [] pre_idx = [-1] * len(nums) for idx, num in enumerate(nums): if not stack&nbs***bsp;num > nums[stack[-1]]: stack.append(idx) pre_idx[idx] = stack[-2] if len(stack) > 1 else -1 else: l, r = 0, len(stack) - 1 loc = r while l <= r: mid = (l + r) // 2 if nums[stack[mid]] >= num: loc = mid r = mid - 1 else: l = mid + 1 stack[loc] = idx pre_idx[idx] = stack[loc - 1] if loc >0 else -1 idx = stack[-1] res = [] while idx != -1: res = [str(nums[idx])] + res idx = pre_idx[idx] return res # return [str(item) for item in val_idx] n = map(int, input().strip()) array = list(map(int, input().strip().split())) # print(array) res = solution(array) print(' '.join(res))