Minimum Maximum Value

In this approach, we will recursively find the maximum and minimum value of every possible subexpression in the given expression. 

To find the maximum/minimum value of the subexpression ‘exp[startIndex, endIndex]’, starting at the position, ‘startIndex’ and ending at ‘endIndex’, we can iterate over the subexpression and if we find an operator at position ‘i’, we can find add/multiply the subexpressions exp[startIndex, i - 1] and exp[i + 1, endIndex], we take the maximum/minimum of all the positions when we find an operand, in the subexpression.

We create two functions maxValue(startIndex, endIndex, exp) and minValue(startIndex, endIndex, exp), where startIndex and endIndex are starting and ending indices of the subexpression of ‘exp’.

The only difference between the functions is that in maxValue we are taking the maximum of all subexpressions, while in minValue we are taking the minimum of all expressions.

Algorithm:

• In the function maxValue(startIndex, endIndex, exp):
  • If startIndex is greater than endIndex return 0
  • If startIndex is equal to endIndex
    • Convert the exp[startIndex] to integer and return it.
  • Set maxAns as negative infinity
  • Iterate i from startIndex to endIndex
    • Set currVal as 0
    • If exp[i] is equal to  ‘+’
      • Set currVal as maxValue(startIndex, i - 1) + maxValue(i + 1, endIndex
    • If exp[i] is equal to  ‘*’
      • Set currVal as maxValue(startIndex, i - 1) * maxValue(i + 1, endIndex
    • Set maxAns as maximum of maxAns and currVal
  • Return maxAns
• In the function minValue(startIndex, endIndex, exp):
  • If startIndex is greater than endIndex return 0
  • If startIndex is equal to endIndex
    • Convert the exp[startIndex] to integer and return it.
  • Set minAns as infinity
  • Iterate i from startIndex to endIndex
    • Set currVal as 0
    • If exp[i] is equal to  ‘+’
      • Set currVal as minValue(startIndex, i - 1, exp) + minValue(i + 1, endIndex, exp)
    • If exp[i] is equal to  ‘*’
      • Set currVal as minValue(startIndex, i - 1, exp) * minValue(i + 1, endIndex, exp)
    • Set minAns as minimum of minAns and currVal
  • Return minAns
• In the original function:
  • Set minAns as minValue(0, length of exp - 1, exp)
  • Set maxAns as maxValue(0, length of exp - 1, exp)
  • Return [minAns, maxAns]

In this approach, we will do the same thing as the previous approach, but since it’s clearly observed that in the previous approach, some ranges are being calculated multiple times. To prevent this we will create a cache that will store solutions for every range So that we don’t have to recalculate it.

We will create the same two functions, maxValue(startIndex, endIndex, exp, cache) and minValue(startIndex, endIndex, exp, cache), where startIndex and endIndex are starting and ending indices of the subexpression of ‘exp’. Cache is the cache of solutions for each range.

Algorithm:

• In the function maxValue(startIndex, endIndex, exp, cache):
  • If startIndex is greater than endIndex return 0
  • If startIndex is equal to endIndex
    • Convert the exp[startIndex] to integer and return it.
  • If cache[startIndex][endIndex] does not equal to -1, return cache[startIndex][endIndex]
  • Set maxAns as negative infinity
  • Iterate i from startIndex to endIndex
    • Set currVal as 0
    • If exp[i] is equal to  ‘+’
      • Set currVal as maxValue(startIndex, i - 1, exp, cache) + maxValue(i + 1, endIndex, exp, cache)
    • If exp[i] is equal to  ‘*’
      • Set currVal as maxValue(startIndex, i - 1, exp, cache) + maxValue(i + 1, endIndex, exp, cache)
    • Set maxAns as maximum of maxAns and currVal
  • Set cache[startIndex][endIndex] as maxAns
  • Return maxAns
• In the function minValue(startIndex, endIndex, exp, cache):
  • If startIndex is greater than endIndex return 0
  • If startIndex is equal to endIndex
    • Convert the exp[startIndex] to integer and return it.
  • If cache[startIndex][endIndex] does not equal to -1, return cache[startIndex][endIndex]
  • Set minAns as infinity
  • Iterate i from startIndex to endIndex
    • Set currVal as 0
    • If exp[i] is equal to  ‘+’
      • Set currVal as minValue(startIndex, i - 1, exp, cache) + minValue(i + 1, endIndex, exp, cache)
    • If exp[i] is equal to  ‘*’
      • Set currVal as minValue(startIndex, i - 1, exp, cache) + minValue(i + 1, endIndex, exp, cache)
    • Set minAns as maximum of minAns and currVal
  • Set cache[startIndex][endIndex] as minAns
  • Return minAns
• In the original function:
  • Set minAns as minValue(0, length of exp - 1, exp)
  • Set maxAns as maxValue(0, length of exp - 1, exp)
  • Return [minAns, maxAns]

In this approach, instead of just using a cache, we will use a smaller ranges solution to build larger ranges solutions. To find the value of the subexpression ‘exp[startIndex][endIndex]’, we will iterate from startIndex to endIndex, and whenever we find an operator in between, say at index ‘K’ we can find the value of the ‘exp[startIndex][k - 1]‘ and ‘exp[k + 1][endIndex]’.

We will separate operands and operators for simplicity.

To find the value of larger subexpressions we have to calculate the value of smaller length subexpressions first.

Algorithm:

• Initialise 2 arrays operators and operands
• Iterate ch through exp
  • If ch is an operator append it in operator array
  • Otherwise,
    • Convert ch into an integer and insert it in oprands array
• Set numOfOperands as size of operands array
• Create two matrices of numOfOperandsXnumOfOperands size maxValues and minValues
• Set all the values minValue as infinity, except if the row is equal to the column, then set it as operands[row]
• Set all the values maxValue as negative infinity, except if the row is equal to the column, then set it as operands[row]
• Iterate rangeLen from 2 to numOfOperands + 1
  • Iterate startIndex from 0 to numOfOprands - rangeLen + 1
    • Set endIndex as startIndex + rangeLen - 1
    • Iterate k from startIndex to endIndex
      • Set currMin and currMax as 0
      • If exp[k] equal to ‘+’
        • Set currMin as minValue[startIndex][k - 1] + minValue[k + 1][endIndex].
        • Set currMax as maxValue[startIndex][k - 1] + maxValue[k + 1][endIndex].
      • If exp[k] equal to ‘*’
        • Set currMin as minValue[startIndex][k - 1] * minValue[k + 1][endIndex].
        • Set currMax as maxValue[startIndex][k - 1] * maxValue[k + 1][endIndex].
    • Set minValues[startIndex][endIndex] as minimum of currMin and minValues[startIndex][endIndex]
    • Set maxValues[startIndex][endIndex] as maximum of currMax, maxValues[startIndex][endIndex]
• Return [minValue[0][numOfOperands - 1], maxValue[0][numOfOperands - 1]]