解题思路：动态规划

这是一道区间dp的题目。首先第一步是把区间从n扩展到2n，这样就不用尾首循环了。

接下来按照区间大小，从小到大循环，先计算小区间的最优解，再计算大区间的最优解。

状态转移方程：dp[l][r] = max(dp[l][j] + dp[j][r] + a[l] * a[j] * a[r])， j ∈ [ l + 1, r - 1 ]

注意本题的数据范围：由于珠子的值满足val <= 1000，因此每次获取的能量不超过10^9；n <= 100表示最多100个珠子，故而能量总和不超过10^11。因此使用long long，并且计算的中途不要对10⁹+7取模（如果你在计算中途对10⁹+7取模，则取模后的值就不是最大值了，可能导致后续的dp错误）。

下面贴出cpp代码。

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

int main() {
    const int mod = 1e9 + 7;
    int n;
    cin >> n;
    vector<int> a(n + n);
    vector<vector<long long>> dp(n + n, vector<long long>(n + n, 0));
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 2; i < n; ++i) {
        for (int l = 0; l < n; ++l) {
            int r = l + i;
            for (int j = l + 1; j < r; ++j) {
                dp[l][r] = max(dp[l][r], dp[l][j] + dp[j][r] + a[l] * a[j] * a[r]);
            }
            if(r < n) dp[l + n][r + n] = dp[l][r];
        }
    }
    long long ans = 0;
    for (int l = 0; l < n; ++l) {
        int r = l + n;
        for (int j = l + 1; j < r; ++j) {
            ans = max(ans, dp[l][j] + dp[j][r] + a[l] * a[j] * a[r]);
        }
    }
    cout << (ans % mod);
}