Came up with this:
f=.u@d
u=.[: c g^:(#@n)
d=.(<_) ; ]
c=.[: > s {~ [: {.@\: #@>@s
g=.}.@n ;~ {.@n ; s h {.@n
n=.>@{:
s=.>&{.
h=.[: ; e&.>
e=.<@[`([ ; [ , ])@.t
t=.{:@[ < ]
f 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
1 2 3 4 5 7 11 19
Let me know if you can optimize it.
> On Sep 2, 2016, at 11:30 AM, Raul Miller <[email protected]> wrote:
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
