CFR 552 E. Vanya and Brackets ( Greedy, Expression Parsing, Python )

題意：
給一個由 '+', '*', '0' ~ '9' 組成的合法數式，要求在任意合法的位置插入一對括弧，求最大可能結果。

資料規模：
The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs + and * .
The number of signs * doesn't exceed 15.

解法：
首先注意到乘法的數量不超過 15 個。
考慮貪心，假設當前一個左端在括弧內，下一個符號是加，接著才是乘。那麼可以大略這樣想：左端當前的和是 s，要考慮是否納入括弧內的值為 v，在後面的乘法待乘的是 x。如果不將 v 納入括弧內，得到的結果是 s + v * x。反之如果納入，則會得到 ( s + v ) * x。顯然，由於數據範圍只有 [ 1, 9 ]，所以在遇見乘號之前，加號都不斷納入，一定不會比較差。這麼一來就有結論，只需檢查左界和右界都為乘法的情形。用 python 的 eval() 函數水過。

時間 / 空間複雜度：
O( 15^2 * | S | ) / O( | S | )

S = input()

ans = 0

for ll in range( len( S ) ):
  if not ( ll == 0 or S[ ll - 1 ] == '*' ): continue
  for rr in range( ll + 1, len( S ) + 1, 1 ):
    if not ( rr == len( S ) or S[ rr ] == '*' ): continue
    ans = max( ans, eval( S[ : ll ] + "(" + S[ ll : rr ] + ")" + S[ rr : ] ) )

print( ans )