a bit of dp : Longest Increasing Subsequence

Given a sequence of number, find a subsequence (may not be consecutive) in the sequence such that the elements are strictly increasing.

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;
}