Part-6 (Longest Increasing Subsequence )

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.


                                                   DYNAMIC PROGRAMMING       


#include<bits/stdc++.h>

using namespace std;


int main()

{
     int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);


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

    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if((arr[i]>arr[j])&&((lis[j]+1)>lis[i]))
               {
                   lis[i]=lis[j]+1;
               }
        }
    }
    sort(lis,lis+n);

    cout<<lis[n-1]<<endl;
    return 0;
}

PROBLEM LINK: https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

                                      USING DYNAMIC PROGRAMMING


// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

#include<bits/stdc++.h>

using namespace std;


int main()

{
    int n;

    cin>>n;

    while(n--){

     int x;

    cin>>x;

     int arr[x];

    for(int i=0;i<x;i++)

    {
       cin>>arr[i];

    }

    int lis[x];

    for(int j=0;j<x;j++)

    {
        lis[j]=1;
    }

    for(int k=0;k<x;k++)

    {
        for(int y=0;y<k;y++)

        {
            if(arr[k]>arr[y]&&((lis[y]+1)>lis[k]))

            {
                lis[k]=lis[y]+1;
            }
        }
    }

    sort(lis,lis+x);

    cout<<lis[x-1]<<endl;

    }
    return 0;
}