# HW 3 - 2
We define the subproblem MAXSUM(i, j) to return maximum possible value the expression can take by adding parentheses for integer array [i .. j]. Instead of keeping two arrays of the value and the sign, we preprocss the sequence to assiociate the sign with the value, and store them in an integer array A[1..n]. In other words, we store the minus operator as the sign for the value to simply the problem. For example, if we have -5-3, we store it as [-5, -3], and we can retrieve the operator by checking its sign. Also, 5-3 is mathematically equivalent to 5+(-3).

The original problem can be solved by MAXSUM(0, n)

For the MAXSUM(i, j) we have:

MAXSUM(i, j):
    if i == j:
        return A[i]
    else:
        return MAX(
            for k in range(i, j):
                first_term = MAXSUM(i, k)
                second_term = MAXSUM(k+1, j)
                    if first_term < 0:
                        max(first_term+second_term, -(abs(first_term)+second_term))
                    else:
                        first_term+second_term
        )

This MAX() notation means finding the max value of all iterations.

Justification:
For each recursive call, we add two pairs of parenthese. Partition at all possible location, and use parenthese to wrap both partition. Then we calculate the sum of max possible value for each partition. This esstially tries all location for all combinations of parantheses, and the max is the max of all possibilities.
To show the correctness of this algorithm, we use proof by contradiction. Assume the value returned v is not the maximum possible. Then there must exist another set of parentheses adding actions that achieves a larger value v1. However, since this algorithm has tried all the combinations of parentheses, it is not possible to find a larger v1 (v1 does not exist). Thus by contradition, the algorithm returns the maxium possible solutions. (In addition, all recursive all is on a shorter array with the same problem defination)