fork download
copy 
  1. //
  2. //
  3. //
  4. //memset(ara, -1, sizeof(ara));
  5. //00000001-00000001-00000001-00000001
  6. //00000000-00000000-00000000-00000001
  7. //11111111-11111111-11111111-11111111
  8. //
  9. //+1 = 00000001
  10. //   = 11111110
  11. //   =        1
  12. //   ------------
  13. //     11111111 (-1)
  14. //
  15. //
  16. //
  17. #include<bits/stdc++.h>
  18. using namespace std;
  19.  
  20. int main()
  21. {
  22.     int n;
  23.     cin>>n;
  24.     int List[n];
  25.     for(int i = 0; i < n; i++)
  26.     {
  27.         cin>>List[i];
  28.     }
  29.  
  30.     int LIS[n], Track[n];
  31.     memset(Track, -1, sizeof(Track));
  32.     for(int i  = 0; i < n; i++)
  33.     {
  34.         LIS[i] = 1;
  35.     }
  36.  
  37.  
  38.     for(int i = 1; i < n; i++)
  39.     {
  40.         for(int j = 0; j < i; j++)
  41.         {
  42.             if(List[j] < List[i])
  43.             {
  44.                 LIS[i] = max(LIS[i], 1+LIS[j]);
  45.                 if (LIS[i] == 1 + LIS[j])
  46.                 {
  47.                     Track[i] = j;
  48.                 }
  49.             }
  50.         }
  51.     }
  52.  
  53.     for(int i = 0; i < n; i++)
  54.     {
  55.         cout<<LIS[i]<<" ";
  56.     }
  57.     cout<<endl;
  58.  
  59.     int mx = INT_MIN, ind;
  60.     for(int i = 0; i< n; i++)
  61.     {
  62.         if(mx < LIS[i])
  63.         {
  64.             mx = LIS[i];
  65.             ind = i;
  66.         }
  67.     }
  68.     cout<<"LIS Length = "<<mx<<endl;
  69.  
  70.     for(int i = 0; i < n; i++)
  71.     {
  72.         cout<<Track[i]<<" ";
  73.     }
  74.     cout<<endl;
  75.     vector<int>ans;
  76.     for(int i = ind; i >= 0; )
  77.     {
  78.         ans.push_back(List[i]);
  79.         i = Track[i];
  80.     }
  81.     for(int i = ans.size()-1; i >= 0; i--)
  82.     {
  83.         cout<<ans[i]<<" ";
  84.     }
  85.  
  86.  
  87. }
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
7
3 4 -1 0 6 2 3
stdout
copy 
1 2 1 2 3 3 4 
LIS Length = 4
-1 0 -1 2 3 3 5 
-1 0 2 3
https://ideone.com/8r1vQg
language:
C++ (gcc 8.3)
created:
12 hours 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!