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

algorithm, arrays, language-agnostic

Solution

Here is a solution that will find a sorted subsequence of fixed size `k+1` by doing `k` passes over the input. Each pass is done left-to-right.

Pass 1: Create an auxiliary array `p1[0..n-1]`. `p1[i]` should store the index `j` of a number which is smaller than `arr[i]` and is on the left side of `arr[i]` (in other words: `j<i` and `arr[j]<arr[i]`). `p1[i]` should contain -1 if there is no such element. (`p1` is the same as the `smaller` array from the solution for size 3).

Pass 2: Create an auxiliary array `p2[0..n-1]`. `p2[i]` should store the index `j` of a number which is smaller than `arr[i]`, is on the left side of `arr[i]`, and such that `p1[j] != -1` (in other words: `j<i`, `arr[j]<arr[i]`, and `p1[j]!=-1`). `p2[i]` should contain -1 if there is no such element.

....

Pass k: Create an auxiliary array `pk[0..n-1]`. `pk[i]` should store the index `j` of a number which is smaller than `arr[i]`, is on the left side of `arr[i]`, and such that `p(k-1)[j] != -1` (in other words: `j<i`, `arr[j]<arr[i]`, and `p(k-1)[j]!=-1`). `pk[i]` should contain -1 if there is no such element.

After the `k`th pass, each element where `pk[i] != -1` corresponds to the largest element in a sorted subsequence of size `k+1`.

Pseudocode for `k`th pass (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

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, you have p3[5] != -1, so a sorted subsequence of size 4 exists. The indices of its elements are: `p1[p2[p3[5]]], p2[p3[5]], p3[5], 5` which is 0,1,3,5

Problem

We are given an array of numbers and we want to find a subsequence of size 4 that is sorted in increasing order. ``` for eg ARRAY : -4 2 8 3 1 5 sorted subsequence of size 4 : -4 2 3 5 ``` PS:There is a way of finding the sorted subsequence of size 3(see this). I am trying to think along the same lines but can't seem to find a solution for 4 integers.

Original source