in reply to Puzzle: Longest Increasing Sequence
Heres my go. Originally I had something that was performing between 2N-1 and N*((N+1)/2), but kaif provided the insight I needed to get it to N log N when he pointed out that you only need to store one path of a given length at any one time.
BTW, I wanted a single routine that could return either the indexes or the actual values, so this is a little clunkier than it need be if you didnt care about the indexes.
Update: I was wrong, the worse case run time for this routine is (N+1)/2*N, which is O(N2).
<Reveal this spoiler or all in this thread>
---
$world=~s/war/peace/g
$world=~s/war/peace/g
In Section
Seekers of Perl Wisdom