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

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