sidef/scripts/RosettaCode/lis_dynamic_programming.sf

#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Longest_increasing_subsequence
#

func lis(a) {
    var l = a.len.of { [] }
    l[0] << a[0]
    1.to(a.len-1).each { |i|
        i.range.each { |j|
            if ((a[j] < a[i]) && (l[i].len < l[j].len+1)) {
                l[i] = [l[j]...]
            }
        }
        l[i] << a[i]
    }
    l.max_by { .len }
}

var a = lis(%i<3 2 6 4 5 1>)
var b = lis(%i<0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15>)

say a
say b

assert_eq(a, [2, 4, 5])
assert_eq(b, [0, 2, 6, 9, 11, 15])