Problem Analysis

This problem requires splitting and merging intervals with maximum profit. The solution naturally fits the interval dynamic programming paradigm.

DP Formulation

For any interval [l, r], we choose a split point j (where l ≤ j < r) and split it into two subintervals: [l, j] and [j+1, r]. The profit consists of three components:

1. Base reward: (a[l] + a[r]) * a[j] — additional gain from splitting at position j
2. Left interval profit: dp[l][j] — optimal profit from the left subinterval
3. Right interval profit: dp[j+1][r] — optimal profit from the right subinterval

The recurrence relation becomes:

dp[l][r] = max over j∈[l, r-1] of: (a[l] + a[r]) * a[j] + dp[l][j] + dp[j+1][r]

Implementation

The solution uses memoized recursion with an additional array to record split posisions for output reconstruction.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
int n, values[MAXN];
int memo[MAXN][MAXN];
int splitPt[MAXN][MAXN];

struct Interval {
    int left, right;
};

int solve(int l, int r) {
    if (l > r) return 0;
    if (memo[l][r] != -1) return memo[l][r];
    
    memo[l][r] = 0;
    for (int k = l; k < r; ++k) {
        int candidate = values[k] * (values[l] + values[r])
                      + solve(l, k) + solve(k + 1, r);
        if (candidate > memo[l][r]) {
            memo[l][r] = candidate;
            splitPt[l][r] = k;
        }
    }
    return memo[l][r];
}

void printSplits() {
    queue<Interval> q;
    q.push({1, n});
    
    while (!q.empty()) {
        Interval cur = q.front();
        q.pop();
        
        if (cur.left == cur.right) continue;
        
        int mid = splitPt[cur.left][cur.right];
        printf("%d ", mid);
        
        q.push({cur.left, mid});
        q.push({mid + 1, cur.right});
    }
}

int main() {
    memset(memo, -1, sizeof(memo));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &values[i]);
    }
    
    printf("%d\n", solve(1, n));
    printSplits();
    
    return 0;
}

Output Strategy

The problem requires printing split points level by level. Using a BFS-style queue traversal ensures we output all splits at the same depth before moving deeper. Starting with the entire interval [1, n], we process each interval, record its split point if it spans multiple positions, and enqueue its two children for further processing.

Complexity Analysis

• Time complexity: O(n³) due to three nested loops (intervals, splits, memoization)
• Space complexity: O(n²) for the DP table and split point records

Correctness Proof

We prove by induction on interval length that solve(l, r) returns the maximum achievable profit for interval [l, r].

Base case: When l > r, the interval is empty, returning 0 is correct.

Inductive step: Assume the theorem holds for all intervals with length less than len = r - l + 1. For interval [l, r], any valid first split must occur at some j where l ≤ j < r. The total profit equals:

(a[l] + a[r]) * a[j] + optimal profit of [l, j] + optimal profit of [j+1, r]

By the inductive hypothesis, solve(l, j) and solve(j+1, r) yield the optimal subinterval profits. Our algorithm evaluates all possible j and selects the maximum, which matches the definition of optimal profit for [l, r]. ∎

Remarks

The BFS output mechanism guarantees all split at depth d are printed before any split at depth d+1, satisfying the problem's traversal order requirement.