Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
ambitious

#### CartesianSequence

Find the longest path down the Cartesian tree.
Programming language:

A non-empty array A consisting of N different integers is given. We are looking for the longest possible sequence built from elements of A, A[B], A[B], ..., A[B[K]], satisfying the following conditions:

• The sequence must be decreasing; that is, A[B] > A[B] > ... > A[B[K]].
• For any two consecutive elements of the sequence, A[B[I]] and A[B[I+1]], all the elements of A between them must be smaller than them; that is, for any J = MIN(B[I], B[I+1]) + 1, ..., MAX(B[I], B[I+1]) − 1, we have A[J] < A[B[I+1]].

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A containing N different integers, computes the maximum length of a sequence satisfying the above conditions.

For example, for the following array A:

A = 9 A = 10 A = 2 A = -1 A = 3 A = -5 A = 0 A = -3 A = 1 A = 12 A = 5 A = 8 A = -2 A = 6 A = 4

the function should return 6.
A sequence of length 6 satisfying the given conditions can be as follows:

A = 12 A = 10 A = 3 A = 1 A = 0 A = -3

Write an efficient algorithm for the following assumptions:

• the elements of A are all distinct;
• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].