fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int solve(vector<int>& arr, int i, int j, int prev) {
  5.     // if (j - i <= 1) return 0;  // Base case: Not enough elements
  6.     if(i>=j)
  7.         return 0;
  8.     int w1 = 0, w2 = 0, w3 = 0;
  9.  
  10.     // Remove last two elements
  11.     if ( prev == arr[j - 1] + arr[j])
  12.         w1 = 1 + solve(arr, i, j - 2, prev);
  13.  
  14.     // Remove first two elements
  15.     if ( prev == arr[i] + arr[i + 1])
  16.         w2 = 1 + solve(arr, i + 2, j, prev);
  17.  
  18.     // Remove first and last element
  19.     if ( prev == arr[i] + arr[j])
  20.         w3 = 1 + solve(arr, i + 1, j - 1, prev);
  21.  
  22.     return max({w1, w2, w3});
  23. }
  24.  
  25. int findMaxMoves(vector<int>& a1) {
  26.     int n = a1.size();
  27.     int maxMoves = 0;
  28.  
  29.     // Try all valid sums from initial pairs
  30.     set<int> possibleSums = {
  31.         a1[n - 2] + a1[n - 1], // Last two elements
  32.         a1[0] + a1[1],         // First two elements
  33.         a1[0] + a1[n - 1]      // First and last element
  34.     };
  35.  
  36.     for (int sum : possibleSums) {
  37.         maxMoves = max(maxMoves, solve(a1, 0, n - 1, sum));
  38.     }
  39.  
  40.     return maxMoves;
  41. }
  42.  
  43. int main() {
  44.     vector<vector<int>> testCases = {
  45.         {3,1,5,3,3,4,2},   // Expected: 3
  46.         {4,1,4,3,3,2,5,2}, // Expected: 4
  47.         {1,9,1,1,1,1,1,1,8,1}, // Expected: 1
  48.         {1,9,8,9,5,1,2},   // Expected: 3
  49.         {1,1,2,3,1,2,2,1,1,2} // Expected: 4
  50.     };
  51.  
  52.     for (auto& test : testCases) {
  53.         cout << findMaxMoves(test) << endl;
  54.     }
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
4
1
3
4
https://ideone.com/S15XkQ
language:
C++14 (gcc 8.3)
created:
39 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!