# Re: [Jprogramming] Greatest Increasing Subsequence

I should probably have gone straight to Knuth, but here's what I managed with Fredman's account of the algorithm. The tacit version is surprisingly easy!!!
```
```
Note that this algorithm does not in general produce the same subsequence as the Wikipedia alternative, but it is of equal length, and is a bit quicker. Also, the subsquence's indices are not available, so it is deficient compared to longascseq etc; the latter are /: -like while lisf and taclisf (below) are
`not.`
```
NB. Fredman/Knuth algorithm as in
NB. https://dx.doi.org/10.1016%2F0012-365X%2875%2990103-X

lisf =: 3 : 0
x   =. y
if. 2>#x do. x return. end.
T      =. {.x
for_xj. }.x do.
if. xj > {:T do.
T     =. T,  xj
else.
m     =. T I. xj
NB.      if. xj < m { T do.   Slight impairment with this test
T    =. xj m } T
NB.      end.
end.
end.
T
)

NB. see how to do tacit amend/append xi in T
NB.    10 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11  NB. 10 <: 11, so insert
NB. 7 9 10
NB.    20 ([ I.~ } ]`(,~)@.(>{:) ) 7 9 11  NB. 20 > 11, so append
NB. 7 9 11 20
doxj =: ([ I.~ } ]`(,~)@.(>{:) )  NB. amend T (rha) with xj (lha)

taclisf =: doxj / @ |.    NB. closed form on array

q =: ?.~ 1000000

timer'(#; 10&{.) longascseq1 q'
+-+----+------------------------------------------------+
|8|1971|647 1210 1309 1399 1450 1688 1993 2006 2349 2729|
+-+----+------------------------------------------------+

timer'(#; 10&{.) lisf q'
+-----+----+------------------------+
|4.238|1971|0 2 4 7 9 12 13 20 28 37|
+-----+----+------------------------+

timer'(#; 10&{.) taclisf q'
+-----+----+------------------------+
|4.742|1971|0 2 4 7 9 12 13 20 28 37|
+-----+----+------------------------+

Space requirements are similar for all 3, at ~ 8.4 Mb,
with lisf <~ taclisf <~ longascseq1 , in this case.

Mike

Please note that I've snipped earlier history (below)
from this correspondence.

On 15/09/2016 09:28, Erling Hellenäs wrote:
```
```The Knuth reference can be downloaded here:

```
```
Youngs tableau is on page 47.

/Erling

On 2016-09-14 23:27, 'Mike Day' via Programming wrote:
```
I suspect it's pretty near optimal. The wikipedia article points at Fredman's paper:
```http://www.sciencedirect.com/science/article/pii/0012365X7590103X
```
analysing an algorithm of Knuth's. He shows that it performs better than
```   n log2(n) - n log2 log2 (n) + O(n)
rather than the O(n logn) cited for the function we've been looking at.

I might have a play at tacit for the algorithm already discussed.

Mike

On 14/09/2016 14:57, Erling Hellenäs wrote:
```
Any ideas about how you could make a substantially faster tacit solution to this problem or how you could make this solution substantially faster? /Erling
```

```
```[ sorry, but I've snipped the rest - Mike]

---
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```