A different approach of O(n^2)


#1

int Solution::lis(const vector &a) {
int n=a.size();
int len[n];
for(int i=0;i<n;i++)
{
len[i]=1;
}
int sub[n];
sub[0]=0;
int max=1;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i]>a[j]&&len[i]<len[j]+1)
{
sub[i]=j;
len[i]=len[j]+1;
}
if(max<len[i])
{
max=len[i];
}

  }

}

return max;
}