Между прочим, жадный алгоритм действительно работает (по крайней мере на этом массиве), если за "жадный" алгоритм принимать "найти наибольшую возрастающую подпоследовательность, выкинуть её из массива, повторить трижды". Результат:
(1, 2, 3, 4, 8, 12), (5, 6, 7 ,11), (9, 13, 17)
13 элементов. 14 сделать нельзя. Код на Powershell:
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 переписан с вики (там код на питоне), cutfrom принимает индексы и возвращает массив, в котором данные индексы выколоты (короче).
Не исключено, что на реальном массиве алгоритм не сработает, однако было бы неплохо такой массив найти.
Апдейт: А я был неправ, "жадный" алгоритм работает далеко не всегда. (Обидно) Код для проверки:
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
}
Здесь в лоб создается массив, состоящий из трех возрастающих подпоследовательностей длиной 100 каждая, перемешанных случайным образом. После чего натравление LISS3 на массив не всегда выдает результат длиной 300.
То есть задача мало того что непроста, но решение "в лоб" имеет приличную погрешность.
(1,5,9,10,11,12),(1,5,6,7,11,12),(1,2,3,4,8,12)? – Peter Olson Jul 31 '15 at 07:18