紀錄每個區間的最大值和最小值,再依運算子決定要取哪些值來做比較
假設我想取exp[i..j]的最大值
則式子可寫成exp[i..k] operation exp[k+1..j]
各運算子的計算如下

switch(operation){
  case '+':
    exp[i..j].max = exp[i..k].max + exp[k+1..j].max
    exp[i..].min = exp[i..k].min + exp[k+1..j].min
    break;
  case '-':
    exp[i..j].max = exp[i..k].max - exp[k+1..j].min
    exp[i..j].min = exp[i..k].min - exp[k+1..j].max
    break;
  case '\*':
    exp[i..j].max = Max(exp[i..k].max\*exp[k+1..j].max, exp[i..k].min\*exp[k+1..j].min)
    exp[i..j].min = Min(exp[i..k].min\*exp[k+1..j].min, Min(exp[i..k].min\*exp[k+1..j].max, exp[i..k].max\*exp[k+1..j].min))

data structure

structure{
  int pos // where to cut
  int combination// 決定兩側是最大值或最小值
}

time complexity
因為有三層迭代次數<=n的迴圈,所以為O(n^3)

時間執行表