# C++ Program to Find Longest Increasing Subsequence

LIS (Longest Increasing Subsequence) problem is used to find the longest subsequence of array which is in sorted order. C++ Program for finding the longest increasing subsequence is given below.

Example:

Let A[]= {10, 22, 9, 33, 21, 50, 41, 60, 80}

Length of Longest Increase subsequence is 6 and LIS is {10, 22, 33, 50, 60, 80}.

PROGRAM:

```#include <bits/stdc++.h>
using namespace std;

int calculate(const vector<int> &A)
{
if(A.size()==0) return 0;

int n=A.size();

int list[n];
for(int i=0;i<n;i++) list[i]=1;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(A[j]<A[i]){
list[i]=max(list[i],list[j]+1);
}
}
}

int result=0;
for(int i=0;i<n;i++){
if(result<list[i]){
result=list[i];
}
}
return result;

}
int main(){

int n;

cout<<"\nEnter the total number of elements: \n";
cin>>n;

cout<<"\nEnter the elements of array:\n";
int num;

std::vector<int> A;

for(int i=0;i<n;i++){
cin>>num;
A.push_back(num);
}

int result=calculate(A);
cout<<"\nThe length of longest increasing subsequence is: "<<result<<"\n";
return 0;
}```

OUTPUT: