C++ Dynamic Programming Tabulation/Iterative Method

programming
Tags: #<Tag:0x00007f242ca09068>

#1

Tabulation

    int Solution::lis(const vector<int> &A) {
    int n=A.size();

    vector<int>dp(n,1);
    
    int gmax=0;
    for(int i=0;i<n;i++)
    {
        int lmax=0;
        for(int j=0;j<i;j++)
            {
                if(A[i]>A[j])
                    lmax=max(lmax,dp[j]);
            }
            
        dp[i]=lmax+1;
        gmax=max(gmax,dp[i]);
    }
    return gmax;
}

This is an Iterative way.