Advertisement
Josif_tepe

Untitled

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