A palindrome is a number or a text phrase that reads the same backwards as forwards. For example, each of the following five-digit integers is a palindrome: 12321, 55555, 45554 and 11611. Write a C++ program that reads in a five-digit integer and determines whether it is a palindrome .

Link will be apear in 30 seconds.

Well done! you have successfully gained access to Decrypted Link.

 Question

Please help me code this in C++

Sample Input:

1

4

1 2 3 4

Sample Output:

16

Solution

Step 1

Here is the detailed and simplified C++ code for the above listed problem statement:

Step 2

C++ Code:

 

#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

const int dr[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dc[] = {0, 1, 1, 1, 0, -1, -1, -1};

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

typedef long long ll;

ll a[65], minR[65][65], sum[65][65];
ll dp[65][65];

ll getMin(int i, int j) {
  if (i > j) return -1000000000LL * 60LL - 1LL;
  return minR[i][j];
}

ll solve(int lef, int rig) {
  if (lef + 1 == rig) {
    return minR[lef][rig] * 2;
  }
  if (dp[lef][rig] != -1000000000LL * 60LL - 1LL) {
    return dp[lef][rig];
  }
  ll ret = minR[lef][rig] * (rig - lef + 1);
  for (int l = lef + 1; l < rig; l++) {
    ret = max(ret, solve(l, rig) + min(minR[lef][l - 1], sum[l][rig]) * ((l - 1) - lef + 1 + 1));
    ret = max(ret, solve(lef, l) + min(minR[l + 1][rig], sum[lef][l]) * (rig - (l + 1) + 1 + 1));
    for (int r = l + 1; r < rig; r++) {
      ll cur = solve(lef, l) + solve(r, rig);
      if (r == l + 1) {
        ll add = min(sum[lef][l], sum[r][rig]);
        ret = max(ret, cur + 2 * add);
      } else {
        ll add = min(sum[lef][l], min(sum[r][rig], getMin(l + 1, r - 1)));
        ret = max(ret, cur + (r - 1 - (l + 1) + 1 + 2) * add);
      }
    }
  }
  return dp[lef][rig] = ret;
}

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    minR[i][i] = sum[i][i] = a[i];
    for (int j = i + 1; j <= n; j++) {
      minR[i][j] = min(minR[i][j - 1], a[j]);
      sum[i][j] = sum[i][j - 1] + a[j];
    }
  }
  for (int i = 1; i < 65; i++) {
      for (int j = 1; j < 65; j++) {
          dp[i][j] = -1000000000LL * 60LL - 1LL;
      }
  }
  cout << solve(1, n) << '\n';
}
int main() {
  fastIo;
  int t; cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

 

Output: