algorithm - Find a sorted subsequence of size 4 in an array in linear time -

we given array of numbers , want find subsequence of size 4 sorted in increasing order.

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

ps:there way of finding sorted subsequence of size 3(see this). trying think along same lines can't seem find solution 4 integers.

here solution find sorted subsequence of fixed size k+1 doing k passes on input. each pass done left-to-right.

pass 1: create auxiliary array p1[0..n-1]. p1[i] should store index j of number smaller arr[i] , on left side of arr[i] (in other words: j<i , arr[j]<arr[i]). p1[i] should contain -1 if there no such element. (p1 same smaller array solution size 3).

pass 2: create auxiliary array p2[0..n-1]. p2[i] should store index j of number smaller arr[i], on left side of arr[i], , such p1[j] != -1 (in other words: j<i, arr[j]<arr[i], , p1[j]!=-1). p2[i] should contain -1 if there no such element.

....

pass k: create auxiliary array pk[0..n-1]. pk[i] should store index j of number smaller arr[i], on left side of arr[i], , such p(k-1)[j] != -1 (in other words: j<i, arr[j]<arr[i], , p(k-1)[j]!=-1). pk[i] should contain -1 if there no such element.

after kth pass, each element pk[i] != -1 corresponds largest element in sorted subsequence of size k+1.

pseudocode kth pass (k>1):

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

example:

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 

after 3 passes, have p3[5] != -1, sorted subsequence of size 4 exists. indices of elements are: p1[p2[p3[5]]], p2[p3[5]], p3[5], 5 0,1,3,5