SHARE
TWEET

Untitled

a guest Jun 18th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  7. #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  8.  
  9. const int N = 1000;
  10. int dp[N + 4];
  11. int n, arr[N + 4], maxLen;
  12. const int MOD = 1e9 + 7;
  13.  
  14. int solve1(int index)
  15. {
  16.     if(index == n)
  17.         return 1;
  18.     if(dp[index] != -1)
  19.         return dp[index];
  20.     int ans = solve1(index + 1);
  21.     for(int k = index + 1; k < n; k++)
  22.     {
  23.         if(arr[k] > arr[index])
  24.             ans = max(ans, max(1, 1 + solve1(k)));
  25.     }
  26.     return dp[index] = ans;
  27. }
  28.  
  29. int main()
  30. {
  31.     IO;
  32.     unsigned long long int t;
  33.     cin >> t;
  34.     for(int test = 1; test <= t; test++)
  35.     {
  36.         cin >> n;
  37.         for(int i = 0; i < n; i++)
  38.             cin >> arr[i];
  39.         memset(dp, -1, sizeof dp);
  40.         maxLen = max(maxLen, solve1(0));
  41.         cout << maxLen;
  42.         memset(arr, 0, sizeof arr);
  43.         if(test < t)
  44.             cout << endl;
  45.     }
  46.     return 0;
  47. }
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
 
Top