Eg:

S = 2, -1, 3, -3, 1, 8, 9

Longest Subsequence: 2, 3, 8, 9

(

**2**, -1,

**3**, -3, 1,

**8**,

**9**)

**There are a lot of ways to do this. For small search space, we can do a complete search, but the complexity grows exponentially with incremental increase in search space.**

Dynamic Programming can solve this problem in \(O(N^2)\) complexity, in which both top-down and bottom-up approach can work. Suppose that we are given \(|s_1|, |s_2|, \ldots, |s_k|\) where \(|s_k|\) is the length of the longest subsequence of the sequence \(a_1, a_2, \ldots, a_k\) which includes \(a_k\) as the last element of \(s_k\). Then to find \(s_{k+1}\), we go through all the list \(s_1, s_2, \ldots, s_k\), and we append \(a_{k+1}\) to \(s_i\) if and only if \(a_i < a_{k+1}\). Then \(s_{k+1}\) is the one with the maximum length.

Another approach is by using Binary Search (wow!). As we go through \(i = 1,2,3,\ldots, k\), we maintain an array of maximum lengths of subsequences we have seen so far, and we check if we build a longer subsequence using \(a_i\). If so, we add \(a_i\) to the array and continue. Otherwise, \(a_i\) is either equal to an element (say \(a_j\) in our array or smaller. Either case, we update the the array by replacing \(a_j\) with \(a_i\) since we can build a subsequence of equal length, but with a smaller last element. Using binary search, we can check for the above cases (whether \(a_i\) is bigger than all elements in our array or if there is such \(a_j\)) in \(O(\log{N})\) time. Overall, we can solve the problem in \(O(M\log{N})\) time.

As an example, UVa 481 - What Goes Up can be solved using binary search:

#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> par; vector<int> dp; vector<int> num; void printout(int idx){ if(idx == -1) return; printout(par[idx]); printf("%d\n", num[idx]); } int main(){ int N,cur=0; while(scanf("%d", &N) != EOF){ num.push_back(N); if(dp.empty()){ dp.push_back(cur); par.push_back(-1); ++cur; continue; } int lo = 0, hi = dp.size()-1, mid; while(lo <= hi){ mid = (hi+lo)/2; if(num[dp[mid]] < N){ lo = mid + 1; } else { hi = mid - 1; } } int it = lo; if(it == dp.size()){ par.push_back(dp[it-1]); dp.push_back(cur); } else { if(it > 0) par.push_back(dp[it-1]); else par.push_back(-1); dp[it] = cur; } ++cur; } cout << dp.size() << endl; printf("-\n"); printout(dp[dp.size()-1]); return 0; }