# 補考 10
### HW4-5


:::spoiler 【題目】
#### 【題目】
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負值` 之類的狀況，所以要探討每個區間最大最小值做運算的狀況(有可能會是兩個子區間的最小值相乘而得到最大值)，首先我們可以將表達式$a_1\ op_1\ a_2\ op_2\cdots\ op_{n-1}\ a_n$的數字 $[\ a_1,a_2,\cdots,a_n\ ]$ 和運算符號 $[\ op_1,op_2,\cdots,op_{n-1}\ ]$ 分開來看。

而我們需要有兩個二維矩陣(數字大小)分別儲存子表達式內最大值`max[i][j]`及最小值`min[i][j]`，代表 `i` 到 `j` 所計算出來的最大值及最小值，而運算符號則放在一維陣列內 `op[n-1]`。

#### 【遞迴式】
assume amount of input is n
$1 \leq i,j \leq n$
$max[i][j],\ min[i][j] = a_i\; ,\;if\;i=j.$
\begin{align*}
max[i][j]\ =\ Max_{i\le k < j}
\begin{cases}
max[i][k] &op[k]\quad max[k+1][j]\\
max[i][k] &op[k]\quad min[k+1][j]\\
min[i][k] &op[k]\quad max[k+1][j]\\
min[i][k] &op[k]\quad min[k+1][j]
\end{cases}，max[i][j]代表subexpression數字i到j裡所算出來的最大值，運算式的Maximum在max[1][n]
\end{align*}
\begin{align*}
min[i][j]\ =\ Min_{i\le k < j}
\begin{cases}
max[i][k] &op[k]\quad max[k+1][j]\\
max[i][k] &op[k]\quad min[k+1][j]\\
min[i][k] &op[k]\quad max[k+1][j]\\
min[i][k] &op[k]\quad min[k+1][j]
\end{cases}，min[i][j]代表subexpression數字i到j裡所算出來的最小值，運算式的Minimum在min[1][n]
\end{align*}

#### 【蘇都扣】

//初始值設定 
n = num_size;
for i from 1 to n:
    max[i][i] = a[i],  min[i][i] = a[i];

//主要部份
get_Max_expression(1,n){
    for q from 1 to n-1:    //不能超過n，固定現在運算的長度。
        for i from 1 to n-q:   //會是以陣列為斜的算下去
            j = i + q;
            (max[i][j],min[i][j]) = sub_expression_result(i, j);
    return max[1][n];
}

//跑遞迴式
sub_expression_result(i, j){
    minimum = INT_MAX, maximum = INT_MIN;
    for k from i to j-1:
        MM = max[i][k] op[k] max[k+1][j];    //op是運算符號
        Mm = max[i][k] op[k] min[k+1][j];
        mM = min[i][k] op[k] max[k+1][j];
        mm = min[i][k] op[k] min[k+1][j];
        maximum = Max(MM, Mm, mM, mm, maximum);
        minimum = Min(MM, Mm, mM, mm, minimum);
    return maximum, minimum;
}

#### 【Example Expression = 3 - 4 * 7 + 6】
| 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 |

$Ans: max[1][4]=-1_\#$

### 【括號】

//主要部份
//maxExp[][], minExp[][] 是用來記錄發生 max, min 時的 expression
get_Max_expression(1,n){
    for q from 1 to n-1:    //不能超過n，固定現在運算的長度。
        for i from 1 to n-q:   //會是以陣列為斜的算下去
            j = i + q;
            (max[i][j],min[i][j],MT,mT,MF,mF) = sub_expression_result(i, j);
            placing_paretheses(maxExp,MT,MF,i,j);
            placing_paretheses(minExp,mT,mF,i,j);
    return max[1][n], maxExp[1][n];
}

//跑遞迴式
//MT, mT 用來記錄當 max, min 發生, k 的值 
//MF, mF 用來記錄當 max, min 發生, 是種組合
sub_expression_result(i, j){
    minimum = INT_MAX, maximum = INT_MIN;
    for k from i to j-1:
        MM = max[i][k] op[k] max[k+1][j];    //op是運算符號
        Mm = max[i][k] op[k] min[k+1][j];
        mM = min[i][k] op[k] max[k+1][j];
        mm = min[i][k] op[k] min[k+1][j];
        maxTemp = Max(MM, Mm, mM, mm);
        minTemp = Min(MM, Mm, mM, mm);
        if maxTemp > maximum // 表 maxTemp 為當前最大
            maximum = maxTemp;
            MT = k;
            MF is the the combination about maximum; //MM, mm, Mm?
        if minTemp < minimum // 表 minTemp 為當前最小
            minimum = minTemp;
            mT = k;
            mF is the the combination about minimum;
    return maximum, minimum, MT, mT, MF, mF;
}

//插入括號
placing_paretheses(Exp[][], T, Flag, i, j){
    switch(Flag)
    {
        case 'MM':
            exp[i][j] = '(' + maxExp[i][T] + op[T] + maxExp[T + 1][j] + ')';
            break;
        case 'Mm':
            exp[i][j] = '(' + maxExp[i][T] + op[T] + minExp[T + 1][j] + ')';
            break;
        case 'mM':
            exp[i][j] = '(' + minExp[i][T] + op[T] + maxExp[T + 1][j] + ')';
            break;
        case 'mm':
            exp[i][j] = '(' + minExp[i][T] + op[T] + minExp[T + 1][j] + ')';
            break;
    }
}

#### 【Example Expression = 3 - 4 * 7 + 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 |