While preparing for my data structures final I came across this problem:

A - a given array of integers of length n.

Propose data structure which supports the following operations:

Init(A) - initialisation of the structure given the array A. Worst case complexity: O(nlogn). LengthOfLongest() - returns the length of the longest monotonically increasing s of A (elements). Worst case complexity: O(1).

I know that it is a well known problem, and I'm aware of the relevant wiki article. However the solution provided there is not intuitive to me.

I was given a hint that this problem can be solved as well with 2-3 rank tree for instance.

Can someone explain me the solution using 2-3 tree?

Example: For array A = {10,9,11,8,12,7,13} The longest subsequence is {10, 11, 12, 13} and its length is 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.