It is there mentioned in Section 8.3 Longest Increasing Sequence
page 290.
We distinguish an increasing sequence from a run, where the elements must be
physical neighbors of each other. The selected elements of both must be
sorted in
increasing order from left to right. For example, consider the sequence
S = {2, 4, 3, 5, 1, 7, 6, 9, 8}
The longest increasing subsequence of S has length 5, including
{2,3,5,6,8}. In fact,
there are eight of this length (can you enumerate them?). There are four
longest
increasing runs of length 2: (2, 4), (3, 5), (1, 7), and (6, 9).
Finding the longest increasing run in a numerical sequence is
straightforward.
Indeed, you should be able to devise a linear-time algorithm fairly easily.
Sorry, After reading it again I see that those should be neighbours.
I have interpreted longest increasing run wrongly.
-Thanks,
Bujji.
On Tue, Dec 17, 2013 at 1:17 PM, Shashwat Anand <[email protected]> wrote:
>
>
>
> On Tue, Dec 17, 2013 at 1:30 AM, bujji jajala <[email protected]>wrote:
>
>> Given an Array of integers (A1,A2,...,An) of length n, Find the maximum
>> possible length of increasing sub sequence formed from A1, A2,....,An.
>>
>>
>> I read that it is possible to compute in linear time as mentioned in
>> algorithm design manual bySkiena.
>>
>
> Interesting. I think I am getting older, I don't recall or probably
> missed it.
> Can you point the page number where it was mentioned, computing LIS in O
> (N) that is.
>
>
>
>> -Thanks
>> Bujji
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
