Advertisement
Josif_tepe

Untitled

Nov 28th, 2023
691
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6. const int maxn = 5005;
  7. int a[maxn], dp[maxn];
  8. int n;
  9.  
  10. int rec(int at) {
  11.     if(dp[at] != -1) {
  12.         return dp[at];
  13.     }
  14.     int res = 1;
  15.     for(int i = at + 1; i < n; i++) {
  16.         if(abs(a[at]) < abs(a[i])) {
  17.             if((a[at] > 0 and a[i] < 0) or (a[at] < 0 and a[i] > 0)) {
  18.                 res = max(res, rec(i) + 1);
  19.             }
  20.         }
  21.     }
  22.     return dp[at] = res;
  23. }
  24. int main()
  25. {
  26.     ios_base::sync_with_stdio(false);
  27.     cin >> n;
  28.    
  29.     for(int i = 0; i < n; i++) {
  30.         cin >> a[i];
  31.         dp[i] = -1;
  32.     }
  33.     int res = 0;
  34.     for(int i = 0; i < n; i++) {
  35.         res = max(res, rec(i));
  36.     }
  37.     cout << res << endl;
  38.     return 0;
  39. }
  40.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement