It seems to me that the "efficient algorithm" documented on the wikipedia page would have an analogous flaw. It is performing binary searches on unsorted lists. That said, it does perform correctly for this example.
Thanks, -- Raul On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming <[email protected]> wrote: > > > Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is > obvious now. I'll try for a correct solution again tomorrow. > > > > > From: 'Mike Day' via Programming > > Sent: Saturday, September 3, 00:26 > > Subject: Re: [Jprogramming] Greatest Increasing Subsequence > > To: 'Mike Day' via Programming > > > > Same problem with my version, which was faster but equally wrong! Mike On > 02/09/2016 14:57, Raul Miller wrote: > 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, > --- > This email has been checked for viruses by Avast antivirus software. > https://www.avast.com/antivirus > ---------------------------------------------------------------------- For > information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
