#include<vector>
#include <iostream>
using namespace std;
int LISdp(int arr[], int n, int currIndex, int maxVal, vector<int> &dp) {
if (currIndex == n) {
return 0;
}
// if (dp[currIndex] != -1) return dp[currIndex];
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 + LISdp(arr, n, currIndex + 1, arr[currIndex], dp);
}
notIncluded = LISdp(arr, n, currIndex + 1, maxVal, dp);
return dp[currIndex] = max(notIncluded, included);
}
int32_t main() {
int n = 6;
// cin >> n;
int arr[] = {6, 3, 7, 4, 6, 9};
vector<int> dp(n, -1);
cout << LISdp(arr, n, 0 , -1, dp);
return 0;
}
