jain12

longest increasing subsequence by dynamic programming

May 1st, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.54 KB | None | 0 0
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;
  4.  
  5. int LIS(int arr[],int n){
  6.   if(n==0|| n==1)
  7.     return n;
  8.   int L[n]={0};
  9.   L[0]=1;
  10.   for(int i=1;i<n;i++){
  11.     for(int j=0;j<i;j++){
  12.       if(arr[j]<arr[i]){
  13.         L[i]=max(1+L[j],L[i]);
  14.         }
  15.       }
  16.       if(L[i]==0)
  17.         L[i]=1;
  18.     }
  19.     int max_len=0;
  20.     for(int i=0;i<n;i++)
  21.         max_len=max(L[i],max_len);
  22.     return max_len;
  23.   }
  24.  
  25. int main(){
  26.   int n=8;
  27.   int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  28.   cout<<LIS(arr,n);
  29.   return 0;
  30.   }
Add Comment
Please, Sign In to add comment