058_longest_increasing_subsequence_DP.cpp

#include<bits/stdc++.h>
using namespace std;

class Solution{
    public:
    int longestSubsequence(int n, int a[]){
        int dp[n];
        dp[0] = 1;
        for(int i=1; i<n; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if (a[i] > a[j]) dp[i] = max(dp[i],dp[j]+1);
            }
        }
        return *max_element(dp, dp + n);
    }
};