Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1 instead of _8 _4 _3 _1.
Here's a brute force O(2^n) approach that I hacked up earlier - it obviously only works on short lists: increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I.@increasing We can do better, of course, but I have some other things I want to deal with, first. Thanks, -- Raul On Thu, Sep 1, 2016 at 10:38 PM, 'Jon Hough' via Programming <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
