There is a dynamic software solution.
For an expression, you can determine that its “split point” is the first statement that is not in any parentheses. Now after this separation, if it is at + , you need to maximize the left sub-expression and the right sub-expression; if it - , then maximize the left side and minimize the right side.
You can use either dynamic programming or memoization to implement this algorithm. Memorization is simple: search for each separation point and save the answer in another data structure (two 2D matrices, with M[x][y] string is the max / min value of the expression starting with x and ending with y ); when data is in matrices, use it instead of recounting.
Using dynamic programming is a bit more complicated, but you can think of it this way:
- firstly, you look at the expression, finding max / min for each consecutive 2 value using the operator between them (well, this is a fashionable way to say, just calculate it);
- swipe through the expression, finding max / min for each consecutive 3 value with an operator between them (for
a ? b ? c , this is calculated assuming the split point is between a and b , and assuming the split point is on b and c and saves max / min values of these two); - Once you know max / min for all
k -length sequences, compute the k + 1 -length tags using the same method as in step 2 until k becomes the length of the array and returns the maximum value for the length k .
This is almost the same as the matrix scaling algorithm , which has complexity O(N^3) . Difficulty can be proved roughly by reasoning: you need to make a cycle N - 1 times, each time no more than N - 1 subsequences, and you need to try no more than N - 1 separation points. So, N ^ 3 temporary difficulty.