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)
• 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]].

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