Only 5 line c++

#1

int Solution::lis(const vector &A)
{
int n=A.size();
int arr[n];int mx=0;
for(int i=0;i<n;i++) arr[i]=1;
for(int i=0;i<n;i++)for(int j=0;j<i;j++) if(A[i]>A[j]) arr[i]=max(arr[i],arr[j]+1);
for(int i=0;i<n;i++)mx=max(mx, arr[i]);
return mx;
}

#2

Hi. Can you please tell me why we are adding the +1 here:
" if(A[i]>A[j]) arr[i]=max(arr[i],arr[j]+1);"
Thanks in advance

#3

thats like saying the maximum length of increasing subsequence till i’th element is

  • Either arr[ i ]
  • Or Maximum length till j + adding ith int from input Array to the longest subsequence till j. ( arr [ j ] + 1 ) the 1 represents the ith element i.e. A[ i ]
#4

Good solution, you can consider doing this instead of using array-
vector<int>dp(n, 1);