Longest Increasing Subsequence Print

#include<bits/stdc++.h>
using namespace std;
int lis(int a[], int n)
{
    int l[n], p[n], i, j, mx = 0, index = -1;

    for(i=0;i<n;i++)
    {
        l[i] = 1;
        p[i] = -1;
    }

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

    for(i=0;i<n;i++)
    {
        if(mx < l[i])
        {
            mx = l[i];
            index = i;
        }
    }

    cout << "\nLongest Increasing Subsequence is :: \n";
    while(index >= 0)
    {
        cout << a[index] << " ";
        index = p[index];
    }

    return mx;
}
int main()
{
    int n, i;
    cout << "Enter Array Size :: ";
    cin >> n;

    int a[n];

    cout << "\nEnter Array Element :: \n";
    for(i=0;i<n;i++)
        cin >> a[i];

    cout << "\n\nLongest Increasing Subsequence Size :: " << lis(a, n) << "\n";

    return 0;
}

Comments