A mathematical expression is given without parentheses. Design an algorithm to parenthesize the expression such that the value of the expression is maximized. For example, consider the expression: 2+7⋅5. There are two ways to parenthesize the expression 2+(7⋅5) = 37 and (2+7)⋅5 = 45, so in this case, your algorithm should output the second expression. Here, you may assume the given expressions contain only 3 kinds of binary operators ‘+’, ‘−’, and ‘⋅’.
因為題目說有 + - *
三種運算符號,因此需要考慮 負值x負值
之類的狀況,所以要探討每個區間最大最小值做運算的狀況(有可能會是兩個子區間的最小值相乘而得到最大值),首先我們可以將表達式的數字 和運算符號 分開來看。
而我們需要有兩個二維矩陣(數字大小)分別儲存子表達式內最大值max[i][j]
及最小值min[i][j]
,代表 i
到 j
所計算出來的最大值及最小值,而運算符號則放在一維陣列內 op[n-1]
。
assume amount of input is n
min | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 3 | -1 | -25 | -49 |
2 | -4 | -28 | -52 | |
3 | 7 | 13 | ||
4 | 6 |
max | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 3 | -1 | -7 | -1 |
2 | -4 | -28 | -22 | |
3 | 7 | 13 | ||
4 | 6 |
max | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 3 | (3-4) | ((3-4)*7) | (((3-4)*7)+6) |
2 | -4 | (4*7) | (4*(7+6)) | |
3 | 7 | (7+6) | ||
4 | 6 |
min | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 3 | (3-4) | (3-(4*7)) | (3-(4*(7+6))) |
2 | -4 | (4*7) | ((4*7)+6) | |
3 | 7 | (7+6) | ||
4 | 6 |