Longest Increasing Subsequence

Longest Increasing Subsequence.cpp

typedef vector<int> vi;
/**
 * LONGEST INCREASING SUBSEQUENCE
 * COMPLEXITY O(N^2)
 */
int lci(vi &A) {
  vi DP (A.size(), 1);

  for(int i=1; i<(int)A.size(); i++) {    
    for(int j=0; j<i; j++) {
        
      if(A[j] < A[i])
        DP[i] = max(DP[i], DP[j] + 1);
          
    }
  }
    
  int maxi = 0;
  for(int i=0; i<DP.size(); i++)
    maxi = max(maxi, DP[i]);
    
  return maxi;
}