1
$\begingroup$

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.

$\endgroup$

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.