fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int lis(int *arr, int n, int index, int last, int *ans){
  6.     if(index >= n){
  7.         return 0;
  8.     }
  9.  
  10.     // memoization sirf 2-d me ho skti hai nhi toh inner loop bhi lagana padega recursion me jisse TC O(n^2) ho jaayegi
  11.  
  12.     int take = 0;
  13.     int dontTake = lis(arr, n, index + 1, last, ans);
  14.     if(arr[index] > last){
  15.         take = 1 + lis(arr, n, index + 1, arr[index], ans);
  16.     }
  17.  
  18.     return max(take, dontTake);
  19. }
  20.  
  21. int lisDP(int *arr, int n){
  22.     int *ans = new int[n + 1];
  23.     ans[0] = 0;
  24.     ans[1] = 1;
  25.     for(int i = 2; i <= n; i++){
  26.         ans[i] = 1;
  27.         for(int j = i - 1; j > 0; j--){
  28.             if(arr[j - 1] < arr[i - 1]){
  29.                 ans[i] = max(ans[j] + 1, ans[i]);
  30.             }
  31.         }
  32.     }
  33.  
  34.     int maxi = -1;
  35.     for(int i = 0; i <= n; i++){
  36.         if(maxi < ans[i]){
  37.             maxi = ans[i];
  38.         }
  39.     }
  40.     delete []ans;
  41.     return maxi;
  42. }
  43.  
  44. int main(){
  45.     int n;cin>>n;
  46.     int *arr = new int[n];
  47.     for(int i = 0; i < n; i++){
  48.         cin>>arr[i];
  49.     }
  50.  
  51.     int *ans = new int[n + 1];
  52.     for(int i = 0; i <= n ;i++){
  53.         ans[i] = -1;
  54.     }
  55.  
  56.     cout<<lisDP(arr, n)<<endl;
  57.     delete []arr;
  58.     delete []ans;
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
1 2 3
4 5 6
7 8 9
stdout
copy 
1
https://ideone.com/OKLHxn
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!