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

Question

我们给出了一组数字,我们希望找到大小为4的子序列,按升序排序.

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

PS:有一种方法可以找到大小为3的排序子序列(见此).我试图沿着相同的路线思考,但似乎无法找到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与smaller大小为3的解决方案中的数组相同).

传递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.

在第kth遍之后,每个元素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], 50,1,3,5