Programming Practice: Longest common subsequence

gistfile1.cpp

// dynamic programming longest common subsequence

#include <iostream>
#include <vector>

int main() {

    const int N = 6;
    int A[N] = {3, 2, 6, 4, 5, 1};

    // L[n] = the longest increasing subsequence that ends with A[n]
    std::vector<std::vector<int> > L(N); 

    // L[0] = {A[n]} initially 
    L[0].push_back(A[0]);

    for(int i=1; i < N; ++i) {
        // find longest A[j] such that tail of A[j] < A[i]
        // we're going to append 
        for(int j=0; j < i; ++j) {
            if( (A[j] < A[i]) && (L[i].size() < L[j].size()+1) ) {
                L[i] = L[j];
            }
        }
        // append a[i] to the end of l[i]
        L[i].push_back(A[i]);
    }

    int longest_idx = 0;
    for(int i = 0; i < N; ++i) {
        if (L[i].size() > L[longest_idx].size()) {
            longest_idx = i;
        }
    }

    std::cout << "The longest increasing subsequence is: " << std::endl;
    for(int i = 0; i < L[longest_idx].size(); ++i) 
        std::cout << L[longest_idx][i] << " ";
    std::cout << std::endl;

    return 0;
}