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
