NN_505

LISgen

Feb 20th, 2021
826
2 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int notVisited = -1;
  5. vector<int> dp, nxtIndx;
  6.  
  7. int f(int indx, vector<int> &v)
  8. {
  9.     if(dp[indx] != notVisited) return dp[indx];
  10.  
  11.     int ans = 0, subans;
  12.     for(int i = indx + 1; i < v.size(); i++) {
  13.         if(v[i] > v[indx]) {
  14.             subans = f(i, v);
  15.             if(subans > ans) {
  16.                 ans = subans;
  17.                 nxtIndx[indx] = i;
  18.             }
  19.             ans = max(ans, f(i, v));
  20.         }
  21.     }
  22.  
  23.     dp[indx] = 1 + ans;
  24.     return dp[indx];
  25. }
  26.  
  27. vector<int> genLis(vector<int> v)
  28. {
  29.     dp.assign(v.size()+1, notVisited);
  30.     nxtIndx.assign(v.size()+1, notVisited);
  31.  
  32.     int ans = 0, subans, si = -1;
  33.  
  34.     for(int i = 0; i < v.size(); i++) {
  35.         subans = f(i, v);
  36.         if(subans > ans) {
  37.             ans = subans;
  38.             si = i;
  39.         }
  40.     }
  41.  
  42.     vector<int> lis;
  43.     lis.reserve(v.size()+1);
  44.  
  45.     while(si != -1) {
  46.         lis.push_back(v[si]);
  47.         si = nxtIndx[si];
  48.     }
  49.     return lis;  
  50. }
  51.  
  52. int main()
  53. {
  54.     int n;
  55.     cin >> n;
  56.  
  57.     vector<int> vec(n);
  58.  
  59.     for(int i=0; i<n; i++) {
  60.         cin >> vec[i];
  61.     }
  62.  
  63.     vector<int> lis = genLis(vec);
  64.     for(auto it : lis) cout << it << ' ';
  65.     cout << '\n';
  66.     return 0;
  67. }
  68.  
RAW Paste Data