class Solution {
public:
    vector<int> v;
    int n;
    int dp[2505];
    int rec(int at) {
        if(dp[at] != -1) {
            return dp[at];
        }

        int result = 1;
        for(int i = at + 1; i < n; i++) {
            if(v[at] < v[i]) {
                result = max(result, rec(i) + 1);
            }
        }
        return dp[at] = result;
    }
    int lengthOfLIS(vector<int> nums) {
        v = nums;
        n = (int) v.size();
        int result = 0;
        for(int i = 0; i < n; i++) {
            dp[i] = -1;
        }
        for(int i = 0; i < n; i++) {
            result = max(result, rec(i));
        }
        return result;
    }
};