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 =. >.@-: 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
