arrays - 在线性时间内找到数组中大小为 4 的已排序子序列

Question

给定一个数字数组，我们想要找到一个大小为 4 且按升序排列的子序列。

for eg ARRAY                :  -4 2 8 3 1 5
sorted subsequence of size 4 : -4 2 3 5

PS:有一种方法可以找到大小为 3(see this)的已排序子序列。我试图按照相同的思路思考，但似乎无法找到 4 个整数的解决方案。

Answer 1

这是一个解决方案，可以找到固定大小的已排序子序列 k+1通过做k通过输入。每次通过都是从左到右完成的。

第 1 步:创建辅助数组 p1[0..n-1] . p1[i]应该存储索引 j小于 arr[i] 的数字并且在 arr[i] 的左侧(换句话说:j<i 和 arr[j]<arr[i] )。 p1[i]如果没有这样的元素，则应包含 -1。 (p1 与大小 3 的解决方案中的 smaller 数组相同)。

第 2 步:创建辅助数组 p2[0..n-1] . p2[i]应该存储索引 j小于 arr[i] 的数字, 在 arr[i] 的左侧，这样 p1[j] != -1 (换句话说: j<i 、 arr[j]<arr[i] 和 p1[j]!=-1 )。 p2[i]如果没有这样的元素，则应包含 -1。

....

传递 k:创建辅助数组 pk[0..n-1] . pk[i]应该存储索引 j小于 arr[i] 的数字, 在 arr[i] 的左侧，这样 p(k-1)[j] != -1 (换句话说: j<i 、 arr[j]<arr[i] 和 p(k-1)[j]!=-1 )。 pk[i]如果没有这样的元素，则应包含 -1。

k之后第遍，每个元素在哪里 pk[i] != -1对应于大小为 k+1 的已排序子序列中的最大元素.

k 的伪代码第遍 (k>1):

function do_kth_pass(pk[], p_k_minus_1[])
    min = -1
    for i in 0..n-1:
        if min != -1 and arr[i] > arr[min]:
            pk[i] = min
        else
            pk[i] = -1
        if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]):
            min = i

例子:

Index:   0  1  2  3  4  5
Array:  -4  2  8  3  1  5
p1:     -1  0  0  0  0  0
p2:     -1 -1  1  1 -1  4
p3:     -1 -1 -1 -1 -1  3

经过 3 次后，您有 p3[5] != -1，因此存在大小为 4 的已排序子序列。其元素的索引是:p1[p2[p3[5]]], p2[p3[5]], p3[5], 5这是 0,1,3,5