最长递增子序列

[编程题]最长递增子序列

热度指数：6930 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

输入描述:

输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr 。

输出描述:

输出一行。代表你求出的最长的递增子序列。

示例1

输入

9
2 1 5 3 6 4 8 9 7

输出

1 3 4 8 9

示例2

输入

5
1 2 8 6 4

输出

1 2 4

说明

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

Python3

lingeoking

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))

stack保存的是从左到右的递增值，但有可能其在原数组中的index顺序并不合法

因此需要另外一个pre_idx来辅助标记以nums[stack[k]]为结尾的序列，其前一个序列在什么位置上，即pre_idx[k]

然后从右往左重建最长序列

发表于 2021-10-14 21:47:56 回复(0)