Longest Increasing Subsequence (LIS) | Dynamic Programming

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl "\n"

#define N 100005

ll arr[N];

ll dp[N];

ll lis(ll i)

{

    if(dp[i]!=-1)return dp[i];

    ll ans;

    ans=1;

    for(ll j=0;j<i;j++)

    {

        if(arr[i]>arr[j])

        ans=max(ans,lis(j)+1);

    }

    return dp[i]=ans;

}

int main()

{

    memset(dp,-1,sizeof(dp));

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   ll n,i;

   cin>>n;

   for(i=0;i<n;i++)cin>>arr[i];

   ll ans;

   ans=0;

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

    {

        ans=max(ans,lis(i));

    }

  cout<<ans<<endl;

    return 0;

}

iterative solution

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl "\n"

#define N 100005

ll arr[N];

ll dp[N];

int main()

{

    memset(dp,0,sizeof(dp));

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   ll n,i,j;

   cin>>n;

   for(i=0;i<n;i++)cin>>arr[i];

   ll ans;

   ans=1;

   dp[0]=1;

   for(i=0;i<n;i++)dp[i]=1;

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

    {

        ll mx;

        mx=0;

        for(j=i-1;j>=0;j--)

        {

            if(arr[i]>arr[j])

            {

               mx=max(mx,dp[j]);

            }

        }

         dp[i]=mx+1;

    }

    ans=0;

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

{

    ans=max(ans,dp[i]);

}

  cout<<ans<<endl;

    return 0;

}