write a recursive function to find longest increasing subsequence using recursion. For example if we have sequence of  { 6, 3, 4, 5, 6, 9, 8 }. The longest increasing subsequence is {3,4,5,6,9} or {3,4,5,6,8} and its length is 5. Your recursive program should print 5 in this test case.

sample program longest increasing subsequence using recursion

#include <iostream>
#include<algorithm>
#include<climits>
using namespace std;

int mx = 0;

void lis(int index, int *arr, int arr_len, int prev, int c) {

	if (index >= arr_len) {
		if (c >= mx)
			mx = c;

		c = 0;
		return;
	}

	lis(index + 1, arr, arr_len, prev, c);

	if (arr[index] > prev) {
		lis(index + 1, arr, arr_len, arr[index], c + 1);
	}
}

int main() {
	int arr[] = { 6, 3, 4, 5, 6, 9, 8 };
	lis(0, arr, sizeof(arr) / sizeof(int), INT_MIN, 0);
	cout << mx << endl;
	return 0;
}

Big O complexity

The time complexity of above program would be O(2^n) where n is length of inputs.  it is exponential, since each function call calls itself twice. The above solution is not efficient and can be solved with O(n^2) complexity through dynamic programming (http://wikistack.com/longest-increasing-subsequence-dynamic-programming/).



Related Contents to follow