Longest Increasing Subsequence (LIS) O(n^2)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define siz 1000005

int a[siz],b[siz];
vector <int> vec;
int n;

int LIS(){
    for(int i=0;i<=n;i++) b[i]=1;

    int mx=0,j,mxx=0;

    for(int i=1;i<n;i++){
        int mx=b[i];
        for(int j=i-1;j>=0;j--){
            if(a[i]>a[j]){
                mx=max(mx,b[j]+b[i]);
            }
        }
        b[i]=mx;
        mxx=max(mx,mxx);
    }

    return mxx;
}
int main()
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&n)==1){

        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);

        int lis=LIS();

        for(int i=n-1;i>=0;i--){
            if(b[i]==lis){
                vec.push_back(a[i]);
                lis--;
            }
            if(lis==0) break;
        }

        reverse(vec.begin(),vec.end());

        for(int i=0;i<vec.size();i++){
            if(i) printf(" ");
            printf("%d",vec[i]);
        }
    }

    return 0;
}