Longest Increasing Subsequence By Dynamic Programming

// (n^2) time complexity

#include<bits/stdc++.h>

using namespace std;

int lis(int a[], int n)

{

    int l[n], i, j, mx = 1;

    for(i=0;i<n;i++)

        l[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;

        }

        if(l[i] > mx)

            mx = l[i];

    }

    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 << "\nLongest Increasing Subsequence Size :: " << lis(a, n) << "\n";

    return 0;

}