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;
	}
}