Hey guys,
I was just trying to implement Longest Increasing Subsequence through recursion. I implemented it and test it on Contest Page. But it's giving me WA.
I know how to implement it through DP. Please don't give links for GOG or others. Just let me know what's wrong with my recursion.
Code -
#include <bits/stdc++.h>using namespace std;int n;int lis(int a[], int i, int last){if(i == n-1){if(a[i] > last){return 1;} else {return 0;}}int with, without;if(i == 0){with = lis(a, 1, last);without = lis(a, 1, INT_MIN);} else {if(a[i] > last){with = lis(a, i+1, a[i]);without = lis(a, i+1, last);} else {return lis(a, i+1, last);}}return max(1 + with, without);}int main(){int t;cin >> t;while(t--){cin >> n;int a[n];for(int i = 0 ; i < n; i++){cin >> a[i];}cout << lis(a, 0, a[0]) << endl;}}