SHARE
TWEET

backtracking LIS

pdpd123 Sep 16th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[2010], h[2010], bac[2010];
  5.  
  6. int main(){
  7.     int n;
  8.     cin >> n;
  9.     for(int i=0; i<n; i++) cin >> h[i];
  10.     for(int i=0;i<n;i++) bac[i] = -1;
  11.    
  12.     // dynamic programming
  13.     for(int i=0; i<n; i++){
  14.         for(int j=0; j<i; j++)
  15.             if(h[j] < h[i])
  16.                 if(dp[j] > dp[i]) dp[i] = dp[j], bac[i] = j;
  17.         dp[i]++;
  18.     }
  19.    
  20.     // find maximum value
  21.     int maxx = -1e18, maxi = 0;
  22.     for(int i=0;i<n;i++){
  23.         if(dp[i] > maxx) maxx = dp[i], maxi = i;
  24.     }
  25.     cout << maxx << endl;
  26.    
  27.     // back tracking
  28.     while(maxi >= 0){
  29.         cout << h[maxi] << ' ';
  30.         maxi = bac[maxi];
  31.     }
  32.     cout << endl;
  33. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top