### PROBLEM LINK:

**Editorialist:** Vaibhav Jain

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Greedy, DP

### PROBLEM:

You are given an expression of n numbers and n-1 operators$(+ or -)$ and you need to maximize expressionâ€™s value by adding valid parenthesis.

### QUICK EXPLANATION:

When we encounter '+' sign our maximum value will be maximum of left and right expressions and when we encounter '-' sign our maximum value will be maximum of left expression and minimum of right expression and vice-versa for minimum values.

### EXPLANATION:

The basic intuition for this solution is based on the thing that whenever we get '-' sign the left expression should be maximum as possible and right expression should be minimum as possible. And when we get '+' sign both expressions should be maximum as possible.

To do above thing we need to memoize. For this we will maintain two 2-D DP matrices as dpMax and dpMin. While dpMax will store the maximum and dpMin will store the minimum in the range. [i][j] will tell us that the range is from i to j.

For implementing we need to have one loop for iterating from second to last element of numbers and we will have a nested loop inside our first loop so that it can calculate all possible ranges from first index till current index of our main loop. And inside our nested loop we will have one loop which will be necessary to get the optimal value for different ranges. The latter loop will iterate over the operators to get us the optimal value.

If you are having difficulty in understanding the above part you can see hidden part for example.

## Click to view

*For input* : 10 - 7 + 50 - 20 + 20 - 100

**End range is 1**

*Start range is 0*

[3 0 1]

**End range is 2**

*Start range is 1*

[57 1 2]

*Start range is 0*

[-47 0 2] [53 0 2]

**End range is 3**

*Start range is 2*

[30 2 3]

*Start range is 1*

[37 1 3] [37 1 3]

*Start range is 0*

[-27 0 3] [33 0 3] [33 0 3]

**End range is 4**

*Start range is 3*

[40 3 4]

*Start range is 2*

[10 2 4] [50 2 4]

*Start range is 1*

[57 1 4] [57 1 4] [57 1 4]

*Start range is 0*

[-7 0 4] [53 0 4] [53 0 4] [53 0 4]

**End range is 5**

*Start range is 4*

[-80 4 5]

*Start range is 3*

[-60 3 5] [-60 3 5]

*Start range is 2*

[110 2 5] [110 2 5] [110 2 5]

*Start range is 1*

[117 1 5] [117 1 5] [117 1 5] [117 1 5]

*Start range is 0*

[93 0 5] [113 0 5] [113 0 5] [113 0 5] [113 0 5]

**Ans** 113

### TIME COMPLEXITY

The time complexity will be O(n^{3}).

### EDITORIALISTâ€™S SOLUTION:

Editorialistâ€™s solution can be found here.