LIS   SIMPLE  O(n2)





#include<iostream>

using namespace std;

int main()
{
int n,i;
cin>>n;

int a[n],maximum[n],maxx=0,j;

maximum[0]=1;

for(i=0;i<n;i++)
cin>>a[i];

for(i=1;i<n;i++)
{
 maxx=0;
 for(j=0;j<i;j++)
 {
  if(a[i]>a[j] && maximum[j]>=maxx)
   maxx=maximum[j];
 }
 maximum[i]=maxx+1;
}
maxx=0;

for(i=0;i<n;i++)
if(maxx<maximum[i])
maxx=maximum[i];

cout<<"LIS is "<<maxx<<endl;

return 0;
}