Range DP

Range DP usually traverse all possible ranges. If we have an array of length n, then traversing all ranges will have the complexity of O(n²)

Maximal Expression

const int N = 210;
int maxf[N][N];
int minf[N][N];
const int INF = 0x3f3f3f3f;
const int NEGINF = 0xcfcfcfcf;
int maxdp(vector<int>& nums, int i, int j);
int mindp(vector<int>& nums, int i, int j);
int mindp(vector<int>& nums, int i, int j) {
    if (i == j) {
        return minf[i][i] = nums[i];
    }
    if (minf[i][j] != INF) return minf[i][j];
    int thismin = INF;
    for (int k = i; k < j; ++k) {
        auto maxleft = maxdp(nums, i, k);
        auto maxright = maxdp(nums, k + 1, j);
        auto minleft = mindp(nums, i, k);
        auto minright = mindp(nums, k + 1, j);
        thismin = min(thismin, maxleft + maxright);
        thismin = min(thismin, maxleft - maxright);
        thismin = min(thismin, maxleft * maxright);
        thismin = min(thismin, minleft + maxright);
        thismin = min(thismin, minleft - maxright);
        thismin = min(thismin, minleft * maxright);
        thismin = min(thismin, minleft + minright);
        thismin = min(thismin, minleft - minright);
        thismin = min(thismin, minleft * minright);
        thismin = min(thismin, maxleft + minright);
        thismin = min(thismin, maxleft - minright);
        thismin = min(thismin, maxleft * minright);
    }
    return minf[i][j] = thismin;
}
int maxdp(vector<int>& nums, int i, int j) {
    if (i == j) {
        return maxf[i][i] = nums[i];
    }
    if (maxf[i][j] != NEGINF) return maxf[i][j];
    int thismax = NEGINF;
    for (int k = i; k < j; ++k) {
        auto maxleft = maxdp(nums, i, k);
        auto maxright = maxdp(nums, k + 1, j);
        auto minleft = mindp(nums, i, k);
        auto minright = mindp(nums, k + 1, j);
        thismax = max(thismax, maxleft + maxright);
        thismax = max(thismax, maxleft - maxright);
        thismax = max(thismax, maxleft * maxright);
        thismax = max(thismax, minleft + maxright);
        thismax = max(thismax, minleft - maxright);
        thismax = max(thismax, minleft * maxright);
        thismax = max(thismax, minleft + minright);
        thismax = max(thismax, minleft - minright);
        thismax = max(thismax, minleft * minright);
        thismax = max(thismax, maxleft + minright);
        thismax = max(thismax, maxleft - minright);
        thismax = max(thismax, maxleft * minright);
    }
    return maxf[i][j] = thismax;
}
int solve(vector<int>& nums) {
    memset(maxf, 0xcf, sizeof maxf);
    memset(minf, 0x3f, sizeof minf);
    if (nums.empty()) return 0;
    const int n = nums.size();
    return maxdp(nums, 0, n - 1);
}

Thanks for reading.