Given a list of numbers, find the greatest increasing subsequence of the list.
e.g if list is 6 1 3 4 2 8 then the greatest increasing subsequence is 1 3 4 8.
My solution:
NB. find greatest increasing subsequence of number list.
NB. example list
l =: 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
NB. running max
max =: __
NB. verb tests for new max, returns 1 if
NB. y is greater than current max, 0 otherwise.
g =: 3 : 0
gr =: 0
if. y > max do.
max =: y
gr=. 1
end.
gr
)
NB. find the indices in increasing subsequence
inc =: ((3 : 'max =: __')](g"0)&.>)"0(]@:<)\. l
NB. get the items with max index count. take the first item.
getmax =: I.@:(= >./)@:>@:(+/&.>) (I.@:>@:{.@:{ + {.@:[) ]
indices =: getmax inc
NB. return the items at given indices.
indices { l
This works fine, but seems overly complicated... and ugly. Any better
solutions?
Also this algorithm is O(n^2) in time, but the most efficient algorithm can be
O(n log n).( https://en.wikipedia.org/wiki/Longest_increasing_subsequence )
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
