PROBLEM LINK:Editorialist: Vaibhav Jain DIFFICULTY:EasyMedium PREREQUISITES:Greedy, DP PROBLEM:You are given an expression of $n$ numbers and $n1$ 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 viceversa 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 2D 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. TIME COMPLEXITYThe time complexity will be $O(n^{3})$. EDITORIALIST'S SOLUTION:Editorialist's solution can be found here. asked 20 Aug '18, 18:44

I spent too long analyzing this during the timed competition (resulting in no score). But the essence of my analysis was this:
This is because two successive minus signs allow the brackets to be placed so as to add all terms succeeding the second minus sign. So in the first of those two cases we force successive minus signs by amalgamating all the intervening terms. In the second case we take the smallest initial negative hit and maximize the rest. With a little more work this could probably be coded up as O$(n)$, maintaining a couple of least subtraction options in a single traversal of the terms. answered 20 Aug '18, 23:59
