Thanks. No problems with line-wrapping in youe mail here!
Naming your function lisEH, and mine lis, I find:
l
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
;lisEH l
1 2 4 4 4 4 5 7 11 19
lis l
1 2 3 4 5 7 11 19
So lisEH appears to miss the 3
Mike
On 08/09/2016 11:53, Erling Hellenäs wrote:
Hi all !
The problem seemed like too much fun so I made my own version. See
below. You will have to fix rows cut by the mail system to run it.
It handles 10000 numbers in some minutes on my computer.
All comments are welcome.
Cheers,
Erling
NB. Draws numbers from the end of the sequence. Each number is placed
in one or more groups.
NB. If the number is less than or equal to the first number in a group
this group is duplicated and
NB. the new number placed first in one of the two groups.
NB. If the number is not less than or equal to the first number in any
group a new group is
NB. created with only this number.
NB. Of the resulting groups which now starts with the new number the
longest group is selected.
NB. All groups which do not start with the new number are kept.
NB. When all numbers are drawn the longest remaining group is selected.
LargestIncreasingSubsequence=: [: SelectFirstGroupOfMaxLength [: > [:
([: DoBetweenElementsInFold&.> / PackElements ,
GroupOfEmptyGroupInitialState) ]
PackElements=: <@+
GroupOfEmptyGroupInitialState=: [: < a:"_
DoBetweenElementsInFold=: [ (( LeftIsNotFirstInGroup +.
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup) # ]
)AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst
AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst=: ] , [
AddGroupWIthLeftIfNoGroups [ PrependLeftInGroups
SelectGroupsWithLeftLessOrEqualToFirstElement
SelectGroupsWithLeftLessOrEqualToFirstElement=:([: , [ <: [: (1 {.
])@> ]) # ]
PrependLeftInGroups=: ( [: < [) ,&.> ]
AddGroupWIthLeftIfNoGroups=:(((0 = [: # ]) {. [: < [),])
FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup=:[:
FirstGroupOfMaxLength LengthOfGroups * LeftIsFirstInGroup
LeftIsFirstInGroup=: [: , [ = [: (1 {. ])@> ]
LengthOfGroups=:([: #@> ])
FirstGroupOfMaxLength=: [: </\ [ = '' $ [: >./ ]
LeftIsNotFirstInGroup=: [: , [ ~: [: ( 1 {. ])@> ]
SelectFirstGroupOfMaxLength=:([: FirstGroupOfMaxLength ([: #@> ]))#]
PackElements 6 1 3 4 2 8
GroupOfEmptyGroupInitialState ''
2 DoBetweenElementsInFold (<1 2 3),<4 5
2 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5
1 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5
8 AppendGroupsWithEmptyLeftOrGroupsWithLeftAppendedFirst (<1 2 3),<4 5
2 SelectGroupsWithLeftLessOrEqualToFirstElement (<1 2 3),<4 5
2 PrependLeftInGroups <4 5
2 AddGroupWIthLeftIfNoGroups 0 {. <i.0
2 AddGroupWIthLeftIfNoGroups , <1 2
2 FirstGroupOfMaxLenghtInGroupsWithLeftFirstInGroup (<2),(<2 4 5),<2 6 7
2 LeftIsFirstInGroup (<1 2 3),<2 4 5
2 LengthOfGroups (<1 2 3),<2 4 5
FirstGroupOfMaxLength 3 3
2 LeftIsNotFirstInGroup (<1 2 3),<2 4 5
2 LeftIsNotFirstInGroup (<1 2 3),<2 4 5
SelectFirstGroupOfMaxLength (<2),(<2 4 5),<2 6 7
LargestIncreasingSubsequence=: LargestIncreasingSubsequence f.
LargestIncreasingSubsequence 6 1 3 4 2 8
l =: 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
LargestIncreasingSubsequence l
LargestIncreasingSubsequence 1000?1000
---
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
