# Longest Increasing Subsequence

## Longest Increasing Subsequence

In the Longest Increasing Subsequence problem, we are asked to find the length of the longest increasing subsequence. It is a very famous problem that is asked in many coding rounds and interviews. Here we provide a c++ solution with an explanation of the problem. ## Longest Increasing Subsequence Problem Desciption

We are given an array of n integers. What is the length of longest increasing subsequence.

Input:

• First line contains integer n – The size of array.
• Second line contains n integers.

Output:

The largest possible length.

## Longest Increasing Subsequence Problem Solution Explanation

### Solution (Top Down):

To build a top down solution we must follow the following steps –

• Break Down the Problem – Let’s suppose we create a function that outputs the length of longest increasing subsequence at index i.

F(i) = Length of Longest Increasing Subsequence ending at i.What can be our transitions?

F(i) = 1 + F(j) where j belongs to [0,i-1] such that arr[j] <= arr[i]

• Find the base case – Base case is int solution of smallest known problem. In this problem we know that F(0) = 1 (ie we only have one element in array and no left before it).
• Check for optimal substructure and overlapping sub problems – It is easy to see that the problem can be broken down into smaller problems. The optimal substructure and overlapping sub problems properties can be visualized below. ### Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int memo[N];
int lis(int arr[], int idx)
{
if (idx == 0)
return 1;
if (memo[idx] != –1)
return memo[idx];

int ans = 1;

for (int i = idx – 1i >= 0i–)
{
if (arr[i] <= arr[idx])
ans = max(ans1 + lis(arri));
}

return memo[idx] = ans;
}
/*
Auxiliary function getting lis ending at every index i
*/
int auxF(int arr[], int n)
{
int ans = 0;
for (int i = n – 1i >= 0i–)
{
ans = max(anslis(arri));
}
return ans;
}
int main()
{
memset(memo, –1, sizeof memo);
int n = 6;
int arr[n] = {132582};
cout <<“Lis is “ << auxF(arrn<< endl;
return 0;
}

### Output

`Lis is 4`

### Bottom up Solution

Here we create a dp array of length n. We iterate over dp array from 0 to n-1. For every index i we check all possible indices j, whether current index i can extend j.

### Code

#include <bits/stdc++.h>
using namespace std;
int lis(int arr[], int n)
{
int dp[n];
int ans = 0;
for (int i = 0i < ni++)
{
dp[i] = 1;
for (int j = 0j < ij++)
{
if (arr[j] <= arr[i])
dp[i] = max(dp[i], 1 + dp[j]);
}

ans = max(ansdp[i]);
}
return ans;
}

int main()
{
int n = 6;
int arr[n] = {132582};
cout << “Lis is” << lis(arrn<< endl;
return 0;
}

### Output

`Lis is 4`