Add Parentheses 3
Time limit1.5sMemory limit512 MB
Parenthesize an alternating digit and +,-,* expression of length up to 19 to maximize its value, respecting left-to-right and multiplication-first rules.
- Level
Hard8 of 10
- Topics
- Divide and conquer, Dynamic programming, Recursion, Brute force
- Solved
- No attempts yet
Problem
You are given an expression of length N. The expression consists of integers between 0 and 9 inclusive and the operators (+, -, ×). Because multiplication has higher precedence than addition and subtraction, multiplication must be evaluated first. When evaluating an expression, you must proceed from left to right. For example, the result of 3+8×7-9×2 is 41.
When you add parentheses to an expression, the subexpression inside the parentheses must be evaluated first. For example, if you add parentheses to 3+8×7-9×2 as (3+8)×7-(9×2), the result of the expression is 59. Nested parentheses may be used, and a pair of parentheses may contain multiple operators. That is, 3+((8×7)-9)×2, 3+((8×7)-(9×2)), and (3+8)×(7-9×2) are all valid expressions, with results 97, 41, and -121.
Given an expression, write a program that finds the maximum value of the result obtainable by adding parentheses appropriately. There is no limit on the number of parentheses added, and you may add none at all.
Input
The first line gives the length of the expression N (1 ≤ N ≤ 19). The second line gives the expression. Every integer in the expression is between 0 and 9 inclusive. The string starts with an integer, and operators and integers alternate. Each operator is one of +, -, *. Here * denotes the × operation, which represents multiplication. Because only valid expressions are given, N is odd.
Output
On the first line, print the maximum value of the result obtainable by adding parentheses appropriately. The answer is less than 2^31 and greater than -2^31.