Classic Optimal Parentheses Inserting ( DP )

Problem Description:
Given an arithmetic sequence, add parentheses freely to create the maximal outcome.
For example, the optimal way to add parentheses for:
5-8+7*4-8+9
would be:
200 = (5 − ((8 + 7) × (4 − (8 + 9))))

Constraints:
1. Only +, -, and *.
2. All values are integers between 0 and 9 inclusive.

Solution:
Take operator as the dividing point, and take only maximal and minimal values in account.
dpmin[ i ][ j ] : minimal outcome for value [ i, j ]
dpmax[ i ][ j ] : maximal outcome for value [ i, j ]
dpmin[ i ][ j ] = min{ dpmin[ i ][ k ] * dpmin[ k + 1 ][ j ], dpmin[ i ][ k ] * dpmax[ k + 1 ][ j ], dpmax[ i ][ k ] * dpmin[ k + 1 ][ j ], dpmax[ i ][ k ] * dpmax[ k + 1 ][ j ] }
dpmax[ i ][ j ] = max{ dpmin[ i ][ k ] * dpmin[ k + 1 ][ j ], dpmin[ i ][ k ] * dpmax[ k + 1 ][ j ], dpmax[ i ][ k ] * dpmin[ k + 1 ][ j ], dpmax[ i ][ k ] * dpmax[ k + 1 ][ j ] }

const ll LINF = 1LL << 62;

ll evaluate( int op, ll a, ll b ){ // a [ op ] b
    if( op == 0 ){ // 0 --> +
        return a + b;
    } else if( op == 1 ){ // 1 --> -
        return a - b;
    } else{ // 2 --> *
        return a * b;
    }
}

void solve(){
    map< char, int > opi;
    opi[ '+' ] = 0;
    opi[ '-' ] = 1;
    opi[ '*' ] = 2;

    string s; cin >> s;
    vi val, op;
    for( int i = 0; i < s.size(); ++i ){
        if( i & 1 )
            op.push_back( opi[ s[ i ] ] );
        else
            val.push_back( s[ i ] - '0' );
    }

    vvl dpmax( val.size(), vl( val.size(), -LINF ) );
    vvl dpmin( val.size(), vl( val.size(), LINF ) );
    for( int i = 0; i < val.size(); ++i )
        dpmax[ i ][ i ] = dpmin[ i ][ i ] = val[ i ];

    for( int len = 2; len <= val.size(); ++len )
        for( int i = 0; i + len <= val.size(); ++i ){
            int j = i + len - 1;
            for( int k = i; k < j; ++k ){
                ll a = evaluate( op[ k ], dpmin[ i ][ k ], dpmin[ k + 1 ][ j ] );
                ll b = evaluate( op[ k ], dpmin[ i ][ k ], dpmax[ k + 1 ][ j ] );
                ll c = evaluate( op[ k ], dpmax[ i ][ k ], dpmin[ k + 1 ][ j ] );
                ll d = evaluate( op[ k ], dpmax[ i ][ k ], dpmax[ k + 1 ][ j ] );
                upmin( dpmin[ i ][ j ], min( min( a, b ), min( c, d ) ) );
                upmax( dpmax[ i ][ j ], max( max( a, b ), max( c, d ) ) );
            }
        }

    cout << dpmax[ 0 ][ val.size() - 1 ] << endl;
}