by The longest increasing sub sequence (LIS) is the problem in which we need to find out the length of the longest increasing sub sequence in the given sequence. In this case, numbers doesn’t require to be in consecutive places.
For eg:
The length of LIS in the sequence {1, 2, 2, 5, 8, 6, 3, 6, 9, 7} is 7 and the longest increasing sub sequence is {1, 2, 2, 5, 6, 6, 7}
Let’s see the code to solve this problem.
#include <stdio.h>
#include <unistd.h>
#include <iostream>
#include <string.h>
using namespace std;
int LIS[20] = {};
int lis (int arr[], int size)
{
int max_lis = 0;
for (int i = 0; i < size; i++)
{
int max = 0;
for (int j = 0; j < i; j++)
{
if (arr[i] >= arr[j] && LIS[j] > max)
max = LIS[j];
}
LIS[i] = max + 1;
}
cout <<"Longest Non decreasing subsequence "<< LIS[size - 1] << endl;
}
int main ()
{
int arr[] = {1, 2, 2, 5, 8, 6, 3, 6, 9, 7};
int size = sizeof(arr) / sizeof (arr[0]);
lis (arr, size);
}
