LIS

#include <iostream>
#include <vector>
using namespace std;


void printLIS(vector<int>& arr)
{
    int i=0;
    cout <<"Length of LIS = ";
    for (int x : arr)
    {
        i++;
    }
    cout<<i;
    cout <<"\nThe LIS is\n";
    for (int x : arr)
    {
        i++;
        cout << x << " ";
    }

    cout << endl;
}


void constructPrintLIS(int arr[], int n)
{

    vector<vector<int> > L(n);


    L[0].push_back(arr[0]);


    for (int i = 1; i < n; i++)
    {

        for (int j = 0; j < i; j++)
        {

            if ((arr[i] > arr[j]) &&
                    (L[i].size() < L[j].size() + 1))
                L[i] = L[j];
        }


        L[i].push_back(arr[i]);
    }


    vector<int> max = L[0];


    for (vector<int> x : L)
        if (x.size() > max.size())
            max = x;


    printLIS(max);
}


int main()
{
    int siz,i;
    cout<<"Enter Arry size\n";
    cin>>siz;
    int arr[siz];
    cout<<"Enter Arry \n";
    for(i=0;i<siz;i++)
    {
        cin>>arr[i];
    }

    int n = sizeof(arr) / sizeof(arr[0]);


    constructPrintLIS(arr, n);

    return 0;
}