Find increasing 3-tuple (sub-sequence)

Problem:
You given an array:
3, 2, 1, 6, 5, 4, 9, 8, 7
you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array.
Answer can have multiple tuples, you have to find any one.
In this array, answer will be 3, 6, 9

Solution:

1. Simple. Time complexity = O(n ^ 2)
• Create an array of indexes, and sort the original array keeping track of the indexes in the second array. Now go through the sorted array and for each element try to find a pair of grater elements whose indexes are increasing. Complexity: time = O(n log n) + O(n ^ 2) = O(n ^ 2), space = O(n)
• Alternatively, traverse the original array starting from the second element and consider it to be the middle of the 3-tuple. Try to find a smaller element at indexes [0..i) and a greater element at (i..n]. Complexity: time = O(n ^ 2), space = O(1)
• As suggested in a comment, the following BST solution won't work for "3, 1, 2, 4".
  Or, build a BST from the original array. Then find an element having two consecutive right children. They are grater than one another due to the BST property, and they are located one after another in the original array because we added them in this order in the BST. Complexity: time = O(n ^ 2) [worst] + O(n) = O(n ^ 2), space = O(n)
2. Advanced.
   Search for Longest Increasing Subsequence and stop after finding three elements of the tuple. Time complexity = O(n log n), space = O(n)

From Wikipedia:

Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the position k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here, because j represents the length of the increasing subsequence, and k represents the position of its termination. Obviously, we can never have an increasing subsequence of length 13 ending at position 11. k ≤ i by definition).

P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at X[P[M[i]]]. Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form

..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].

Another explanation for the above dynamic programming solution:
In general, we have set of active lists of varying length. We are adding an element A[i] to these lists. We scan the lists (for end elements) in decreasing order of their length. We will verify the end elements of all the lists to find a list whose end element is smaller than A[i] (floor value).

Our strategy determined by the following conditions,

1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.

2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].

3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.

Note that at any instance during our construction of active lists, the following condition is maintained.

“end element of smaller list is smaller than end elements of larger lists”.

It will be clear with an example, let us take example from wiki {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

A[0] = 0. Case 1. There are no active lists, create one.
0.
----------------------------------------------------------
A[1] = 8. Case 2. Clone and extend.
0.
0, 8.
----------------------------------------------------------

A[2] = 4. Case 3. Clone, extend and discard.
0.
0, 4.
0, 8. Discarded
----------------------------------------------------------

A[3] = 12. Case 2. Clone and extend.
0.
0, 4.
0, 4, 12.
----------------------------------------------------------

A[4] = 2. Case 3. Clone, extend and discard.
0.
0, 2.
0, 4. Discarded.
0, 4, 12.
----------------------------------------------------------

A[5] = 10. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 10.
0, 4, 12. Discarded.
----------------------------------------------------------

A[6] = 6. Case 3. Clone, extend and discard.
0.
0, 2.
0, 2, 6.
0, 2, 10. Discarded.
----------------------------------------------------------

A[7] = 14. Case 2. Clone and extend.
0.
0, 2.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[8] = 1. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2. Discarded.
0, 2, 6.
0, 2, 6, 14.
----------------------------------------------------------

A[9] = 9. Case 3. Clone, extend and discard.
0.
0, 1.
0, 2, 6.
0, 2, 6, 9.
0, 2, 6, 14. Discarded.
----------------------------------------------------------

A[10] = 5. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 5.
0, 2, 6. Discarded.
0, 2, 6, 9.
----------------------------------------------------------

A[11] = 13. Case 2. Clone and extend.
0.
0, 1.
0, 1, 5.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[12] = 3. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 5. Discarded.
0, 2, 6, 9.
0, 2, 6, 9, 13.
----------------------------------------------------------

A[13] = 11. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 2, 6, 9.
0, 2, 6, 9, 11.
0, 2, 6, 9, 13. Discarded.
----------------------------------------------------------

A[14] = 7. Case 3. Clone, extend and discard.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9. Discarded.
0, 2, 6, 9, 11.
----------------------------------------------------------

A[15] = 15. Case 2. Clone and extend.
0.
0, 1.
0, 1, 3.
0, 1, 3, 7.
0, 2, 6, 9, 11.
0, 2, 6, 9, 11, 15. <-- LIS List
----------------------------------------------------------

Complexity:

time - O(n log n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=21602662
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/