/**
 * @file lcs.cpp
 * @author Shirish Reddy <shirishreddy89@gmail.com>
 *
 * finding the longest common subsequence given an array of elements
 */

#include <iostream>
#include <list>
using namespace std;

/**
 * append - appends the values to the given vector and returns the vector
 * 
 * @param value to be appended
 * @param vector to which value is to be appended
 * @return the appended vector
 */
list<int> append(int val1, list<int> v)
{
	v.push_front(val1);
	return v;
}

/**
 * lcs - finds the longest commmon subsequence
 *
 * @param arrays and their sizes from which lcs is to be obtained
 * @return list - the longest common subsequence
 */	
list<int> lcs(int a[], int an, int b[], int bn)
{
	
	//int array[(an<bn ? an : bn)], i=0, discard  ;
	
	list<int> v;
	list<int> discard_a;
	list<int> discard_b;
	if( an == 0 || bn == 0) {
	//if we are at the end of either list, then lcs is empty
		return v;
	}
	else if(a[0] == b[0] ) {
	//if the start element is the same is both then it is on LCS
	//so we just recurse reminder of both of lists
		return append(a[0], lcs(&a[1], an-1, &b[1], bn-1));
		
	}
	else {
	//we don't know which list we should discard from, try both ways, pick which ever is better
		list<int> result;
	//discard a[0] and pass rest of a i.e a[1...]
		discard_a = lcs(&a[1], an-1, b, bn);
		discard_b = lcs(a, an, &b[1], bn-1);
		
		if(discard_a.size() > discard_b.size())
			result = discard_a;
		else
			result = discard_b;
		return result;
	}
}
	
int main()
{
	int a[] = {1,2,4,8,16,32};
	int b[] = {1,2,3,32,8};
	int c[] = {32,16,8,4,2,1};
	int d[] = {8,32,3,2,1};
	//for finding more than one common subsequence insert the reversed arrays to the function lcs so that relative order is still maintained
	//and the other equal sized sequence can be obtained
	list<int> v = lcs(c, 6, d, 5);
	list<int> :: iterator it;
	for(it = v.begin(); it!=v.end(); it++)
		cout<<*it<<endl;
	return 0;
}

32
2
1