Longest Increasing Subsequence(cpp,dp)

Longest Increasing Subsequence

 

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

==============================================================================

code=

class Solution {
public:
    int lengthOfLIS(vector<int>& a) 
    {
        if(a.size()==0)
            return 0;
        
        int dp[a.size()];
        for(int i=0;i<a.size();i++)
            dp[i]=1;
        
        int j=0;
        for(int i=1;i<a.size();i++)
        {
            while(j<i)
            {
                if(a[j]<a[i])
                {
                    dp[i]=max(dp[i],1+dp[j]);
                }
                j++;
            }
            j=0;
        }
        sort(dp,dp+a.size());
        return dp[a.size()-1];
        
    }
};