Longest Increasing Subsequence

/*
Assume you have an array ie. dp where dp[j]=maximum size of longest increasing subsequence ending at j.
suppose you are at ith position so it can be added next to any subsequence which is ending at jth position
and arr[j]<arr[i].so you already have the longest increasing subsequence ending at j as dp[j] so now one
element you are increasing in that subsequence so arr[i] can be dp[j]+1.
We need maximum longest subsequence so take dp[i]=max(dp[j]+1,dp[i]);
Initially dp array will be having 1 because each element alone make 1 size subsequence.
*/

class Solution {
public:
    int lengthOfLIS(vector<int>& arr) {
        vector <int> dp(arr.size(),1);  //dp[i] will tell that longest string possible ending at ith index at array so search
        int _max=1;                     //from j=0 to j<i and if(arr[j]<arr[i]),means ith element can be added to the subsequence
        for(int i=1;i<arr.size();i++){   //ended at jt position because dp[j] contains the length of maximum subsequence ending at
            for(int j=0;j<i;j++){        // jth position so dp[i]=maximum of all dp[j]+1 where arr[j]<arr[i].
                if(arr[j]<arr[i]) dp[i]=max(dp[i],dp[j]+1);   //our result subsequence will definitely end at some point of array,
            }                                                 //so maximum of whole dp array array will be our answer.
            _max=max(_max,dp[i]);
        }
        return _max;
    }
};