# 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.

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
\$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) }