Question

3. [25 points] Here's another example of using dynamic programming over intervals (like we saw with the RNA Secondary Structure problem) You're given an arithmetic expression consisting of positive integers separated by +s and s but without parentheses, and the goal is to determine the maximum possible value the expression could have by inserting parentheses in some way. For example, with 9-1+9-1 the max value is (9-1)(9-1) 16 (by the way, ((9-1)+9)-1 is an alternative parenthesization that achieves this value), whereas for 1-9+ 1-9 the max value is 1-((9 + 1)-9) = 0. For 1+8-3+9-5+6+7-2-4the max value is 1- ((((8-(3+9))-5)-(6+7))-(2+4))- 29 The input will be represented as two arguments: the list of numbers and the list of operations; e.g., 1+8-3+9-5+6+7-2-1 s represented as a= [1, 8, 3, 9, 5, 6, 7, 2, 4] and b-[', '-', '+', '-', '+', '+', '-', '-']. For each interval-say the numbers at indices i through j in a you should have two subproblems, one for that subexpression's ible value, and one for its minimum possible value. Solve the subproblems in

Answer 1

#include <cassert>

#include <string>

#include <vector>

#include <cstring>

#include <climits>

#include <cmath>

using std::vector;

using std::string;

using std::max;

using std::min;

long long eval(long long a, long long b, char op) {

if (op == '*') {

return a * b;

} else if (op == '+') {

return a + b;

} else if (op == '-') {

return a - b;

} else {

assert(0);

}

}

long long get_maximum_value(const string &exp) {

int length = exp.size();

int numOfnum = (length + 1) / 2;

long long minArray[numOfnum][numOfnum];

long long maxArray[numOfnum][numOfnum];

memset(minArray,0,sizeof(minArray)); // initialize to 0

memset(maxArray,0,sizeof(maxArray));

for (int i = 0; i < numOfnum; i++)

{

//The values on the main diagonal is just the number themselves

minArray[i][i] = std::stoll(exp.substr(2*i,1));

maxArray[i][i] = std::stoll(exp.substr(2*i,1));

}

for (int s = 0; s < numOfnum - 1; s++)

{

for (int i = 0; i < numOfnum - s - 1; i++)

{

int j = i + s + 1;

long long minVal = LLONG_MAX;

long long maxVal = LLONG_MIN;

// find the minimum and maximum values for the expression

// between the ith number and jth number

for (int k = i; k < j; k++ )

{

long long a = eval(minArray[i][k],minArray[k + 1][j],exp[2 * k + 1]);

long long b = eval(minArray[i][k],maxArray[k + 1][j],exp[2 * k + 1]);

long long c = eval(maxArray[i][k],minArray[k + 1][j],exp[2 * k + 1]);

long long d = eval(maxArray[i][k],maxArray[k + 1][j],exp[2 * k + 1]);

minVal = min(minVal,min(a,min(b,min(c,d))));

maxVal = max(maxVal,max(a,max(b,max(c,d))));

}

minArray[i][j] = minVal;

maxArray[i][j] = maxVal;

}

}

return maxArray[0][numOfnum - 1];

}

int main() {

string s;

std::cin >> s;

std::cout << get_maximum_value(s) << '\n';

}

#include <iostream>