fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     int N;
  9.     cin >> N;
  10.     vector<int> A(N);
  11.     for (int i = 0; i < N; i++) {
  12.         cin >> A[i];
  13.     }
  14.  
  15.     vector<vector<int>> dp(N, vector<int>(N, 0));
  16.  
  17.     int maxSize = 0;
  18.     for (int i = 0; i < N; i++) {
  19.         dp[i][i] = A[i];
  20.         maxSize = max(maxSize, A[i]);
  21.     }
  22.  
  23.     for (int len = 2; len <= N; len++) {  
  24.         for (int i = 0; i + len - 1 < N; i++) {
  25.             int j = i + len - 1;
  26.  
  27.             for (int k = i; k < j; k++) {
  28.                 if (dp[i][k] && dp[k + 1][j] && dp[i][k] == dp[k + 1][j]) {
  29.                     dp[i][j] = dp[i][k] + dp[k + 1][j];
  30.                     maxSize = max(maxSize, dp[i][j]);
  31.                 }
  32.             }
  33.  
  34.             for (int a = i, b = j; a < b - 1;) {
  35.                 int leftSum = dp[i][a];
  36.                 int rightSum = dp[b][j];
  37.                 if (leftSum && rightSum && leftSum == rightSum && dp[a + 1][b - 1]) {
  38.                     dp[i][j] = leftSum + dp[a + 1][b - 1] + rightSum;
  39.                     maxSize = max(maxSize, dp[i][j]);
  40.                     break;
  41.                 } else if (leftSum < rightSum) {
  42.                     a++;
  43.                 } else {
  44.                     b--;
  45.                 }
  46.             }
  47.         }
  48.     }
  49.  
  50.     cout << maxSize << endl;
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
7
47 12 12 3 9 9 3
stdout
copy 
48
https://ideone.com/LhR3d3
language:
C++14 (clang 8.0)
created:
2 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!