[Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

Well, assuming for now that it does work,  here's an attempt at a J 
version of
the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

lis =: 3 : 0   NB. longest increasing subsequence
m       =. 0#~>:n   =. #x   =. y
L       =. #p       =. ''
mx      =. m{x NB. added this vector for better look-up of x{~mid{m
for_i. i.n do.
   'lo hi' =. 1, L
    xi     =. i{x
    while. lo <: hi do.
       mid    =. >. at -: lo + hi
NB.       if. xi > x{~ mid{m do. NB. next line a bit better
       if. xi > mid{mx do.
          lo =. >: mid
       else.
          hi =. <: mid
       end.
    end.
    p     =. p, m{~<:lo
    m     =. i  lo } m
    mx    =. xi lo } mx    NB. update my additional array
    L     =. L >. lo
NB. smoutput i; (x{.~ >:i); L{.m   NB. diagnostic
end.
|. x{~(p{~])^:(i.L) L{m
)

It's reasonably fast on ?10000#5000 - but possibly wrong!It does
fail on an empty array.

Mike


On 02/09/2016 17:30, Raul Miller 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,
>


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus