Advertisement
Josif_tepe

Untitled

Oct 27th, 2021
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int n;
  5. int niza[10050];
  6. int dp[10050][2];
  7. int fc(int i, int razlika){
  8.     if(i==n){
  9.         return 0;
  10.     }
  11.     if(dp[i][razlika]!=-1){
  12.         return dp[i][razlika];
  13.     }
  14.     int result=0;
  15.     if(razlika==0){
  16.     for(int j=i+1; j<n; j++){
  17.     if(niza[i]-niza[j]>0){
  18.         result=max(result, fc(j, 1)+1);
  19.     }
  20.     }
  21.     }
  22.  
  23.     if(razlika==1){
  24.     for(int j=i+1; j<n; j++){
  25.     if(niza[i]-niza[j]<0){
  26.         result=max(result, fc(j, 0)+1);
  27.     }
  28.     }
  29.     }
  30.     return dp[i][razlika] = result;
  31. }
  32.  
  33.  
  34.  
  35.  
  36. int main()
  37. {
  38.  
  39. cin>>n;
  40. for(int i=0; i<n; i++){
  41.     cin>>niza[i];
  42.     dp[i][0] = dp[i][1] =-1;
  43. }
  44. int cikcak=0;
  45. for(int i=0; i<n; i++){
  46. cikcak=max(cikcak, fc(i, 0));
  47. cikcak=max(cikcak, fc(i, 1));
  48. }
  49.  
  50. cout<<cikcak + 1 << endl;
  51.  
  52. return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement