# find longest increasing subsequence using recursion

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#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/).
**

## Leave a Reply