Algorithm – choose the three longest increasing subsequences

Question:

You are given a long line array. Obviously, an increasing subsequence of elements can be selected from it. I need to select three such subsequences so that their total length is the largest possible.

How to do it?

Greedy algorithms can be proposed with a justification for correctness. For an array (1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12) the "dumb" greedy algorithm will give a choice of 5 + 4 + 3 = 12 elements, while as in fact, you can choose 13 . Finding the maximum amount accurately is critical. If there are several options with the same maximum, you can take any of them.

Sequence selection rules: the selected three sequences should not intersect with each other by any elements.

Answer:

By the way, the greedy algorithm really works (at least on this array) if the "greedy" algorithm is taken as " find the largest increasing subsequence , throw it out of the array, repeat three times". Result:

(1, 2, 3, 4, 8, 12), (5, 6, 7 ,11), (9, 13, 17)

13 elements. 14 cannot be done. Powershell code:

function liss ([int64[]] $x) {
    $m=new-object int64[] ($x.length)
    # хэш-таблица затеяла сбоить даже при приведении типов. 
    # То ли где-то переменная не того типа оказалась, то ли ещё что - заменил в лоб на массивы
    $p=new-object int64[] (1+$x.length)
    $l=0
    $xl=$x.length
    foreach ($i in 0..($xl-1)) {
        $lo=1
        $hi=$l
        while ($lo -le $hi) {
            $mid=[Math]::Ceiling(($lo+$hi)/2)
            if ($x[[int]$m[$mid]] -le $x[$i]) { # заменить -le на -lt если возрастание строгое
                $lo=$mid+1
            } else {
                $hi=$mid-1
            }
        }
        $newL=$lo
        $p[$i]=$m[$newl-1]
        $m[$newL]=$i
        if ($newL -gt $l) { $l = $newL }
    }
    $s=@()
    $k=[int]$m[$l]
    foreach ($i in ($l-1)..0) {
        $args=@{}
        $args["index"]=$k
        $args["value"]=$x[$k]
        $o=new-object psobject -prop $args

        $s=@($o)+$s
        $k=[int]$p[$k]
    }
    return $s
}

function cutfrom ([int64[]] $x, [Object[]] $seq) {
    $a=@()
    $vs=$seq | select -expand index
    foreach ($i in 0..($x.length-1)) {
        if ($i -notin $vs) { $a+=$x[$i] }
    }
    return $a
}

function liss3 ([int64[]] $x) {
    $seq1=liss $x
    $x1=cutfrom $x $seq1
    $seq2=liss $x1
    $x2=cutfrom $x1 $seq2
    $seq3=liss $x2
    write-debug "LISS3 remainder: $((cutfrom $x2 $seq3).length)" # не всегда 0
    $res=@($seq1.value)+@($seq2.value)+@($seq3.value)
    return $res
}
liss3 @(1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12)

liss rewritten from the wiki (there is python code), cutfrom takes indices and returns an array in which the given indices are punctured (in short).

It is possible that the algorithm will not work on a real array, but it would be nice to find such an array.

Update: And I was wrong, the "greedy" algorithm does not always work. (Offensive) Code to check:

function shuffle ([int64[][]] $x) {
    if ($x.length -eq 1) { return $x[0] } # one array, wrapped. Nothing to shuffle
    $m=new-object int64[] ($x.length)
    $max=1
    $thesum=[int]0
    foreach ($a in ($x.length-1)..0) {
        $m[$a]=$x[$a].length
        $thesum+=$m[$a]
        if ($m[$a] -gt $max) { $max=$m[$a] }
    }
    if ($max -eq 1) { return $x } # one array, nothing to shuffle
    $al=new-object system.collections.arraylist
    $rng=new-object system.random
    while ($thesum -gt 0) {
        $d=$rng.next($thesum)
        $i=[int]0
        while (($m[$i]) -le $d -and $i -le $m.length) {
           $d-=$m[$i]
            $i+=1
        }
        $m[$i] -= 1
        $null=$al.add($x[$i][$m[$i]])
        $thesum-=1
    }
    $al.reverse()
    return [object[]]$al
}

function test () {
    $b=1000
    $rng=new-object system.random
    foreach ($a in 1..100) {$a1+=@($b);$b+=$rng.next(2,14) }
    $b=100
    foreach ($a in 1..100) {$a2+=@($b);$b+=$rng.next(2,28) }
    $b=1111
    foreach ($a in 1..100) {$a3+=@($b);$b+=$rng.next(3,16) }
    $ad=shuffle $a1,$a2,$a3
    return $ad
}

Here, an array is created head-on, consisting of three ascending subsequences of 100 each, randomly mixed. After that, setting LISS3 on the array does not always produce a result of 300 length.

That is, the task is not only difficult, but the "head-on" solution has a decent margin of error.

Scroll to Top