1234567891011121314151617181920212223242526272829 |
- #!/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])
|