CareerCup

Let us parse the expression into an array of lexical tokens, tokens[2*N:0] such that:
- tokens[2*i] i=0,N are the number values
- tokens[2*i-1], i=1,N are the operator values

For each pair of indices (i,j), 0 <= i <= j <= N we define:
• Exp(i,j) = the set of all the expressions can be built with the tokens from 2*i to 2*j
• Min(i,j) = the min value of all the expressions in Exp(i,j)
• Max(i,j) = the max value of all the expressions in Exp(i,j)

Max(0,N) is the max value for the entire expression.

We use dynamic programming to compute Min and Max, based on a few recursive equations.
We cache the computed values as two hash tables, hashMin, hashMax.

(int,int) computeMinMax(int i, int j) {
	// If the pair (i,j) was already processed, use the values stored in the hash tables
	if (hashMin(i,j) and hashMax(i,j))) 
return (hashMin(i,j), hashMax(i,j))

	// If i == j, then Exp(i,j) has the unique expression tokens[i]
	if (i == j) {
	    hashMin(i,j) = tokens[i];
	    hashMax(i,j) = tokens[i];
	    return (tokens[i], tokens[i]);
	}

	// If i < j, explore all the expressions in Exp(i,j), based on the top operator tokens[2*k-1]
	int Min_i_j = MinInt;
	int Max_i_j = MaxInt
	for (int k = i+1; k <=j; k ++) {
		(Min_Left, Max_Left) = ComputeMinMax(i,k-1); 
		(Min_Right, Max_Right) = ComputeMinMax(k,j); 
		string operator = tokens[2*k-1];
		if (operator == “-‘) {
			Min_i_j = min(Min_i_j, Min_Left – Max_Right)
			Max_i_j = max(Max_i_j, Max_Left – Min_Right)
		}
		else { // operator = “+”
			Min_i_j = min(Min_i_j, Min_Left + Min _Right)
			Max_i_j = min(Max_i_j, Max_Left + Max_Right)
		}	
            }
	hashMin(i,j) = Min_i_j
	hashMax(i,j) = Max_i_j;
	return (Min_i_j, Max_i_j)	
}

Complexity: O(N^3).
There are O(N^2) pairs (i.j). For each pair we compute Min(i,j), Max(i,j) at most once, thanks to the caching. Iterating over k from i+1 to j, takes O(N), so the total is O(N^2 * N) = O(N^3)

I dont think there is a greedy approach to the problem