Circular Array Trensformation

To handle circular arrangements, duplicate the necklace elements:

for (int idx = 0; idx < n; idx++)
    elements[idx + n] = elements[idx];

Dynamic Programming Formluation

Define energyMatrix[i][j] as the maximum energy obtianed by merging the interval from index i to j. The state transition equation is:

\[ \text{energyMatrix}[i][j] = \max_{k=i+1}^{j-1} \left( \text{energyMatrix}[i][k] + \text{energyMatrix}[k][j] + \text{elements}[i] \cdot \text{elements}[j] \cdot \text{elements}[k] \right) \]

Implementation Approach

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_LENGTH = 205;
int elements[MAX_LENGTH], energyMatrix[MAX_LENGTH][MAX_LENGTH];

int main() {
    int n, maxEnergy = 0;
    cin >> n;
    for (int idx = 1; idx <= n; idx++) {
        cin >> elements[idx];
        elements[idx + n] = elements[idx];
    }
    
    for (int len = 2; len <= n; len++) {
        for (int start = 1; start + len <= 2 * n; start++) {
            int end = start + len;
            for (int mid = start + 1; mid < end; mid++) {
                energyMatrix[start][end] = max(energyMatrix[start][end],
                    energyMatrix[start][mid] + energyMatrix[mid][end] 
                    + elements[start] * elements[end] * elements[mid]);
            }
        }
    }
    
    for (int idx = 1; idx <= n; idx++)
        maxEnergy = max(maxEnergy, energyMatrix[idx][idx + n]);
    
    cout << maxEnergy;
    return 0;
}