一、題目

給定N個加號、M個減號以及N＋M＋1個整數(shù)A1,A2,.… ,AN+M+1，小明想知道在所有由這N個加號、M個減號以及N＋M＋1個整數(shù)湊出的合法的后綴表達(dá)式中，結(jié)果最大的是哪一個?請你輸出這個最大的結(jié)果。
例如使用123+-，則"23+1-"這個后綴表達(dá)式結(jié)果是4，是最大的。
第一行包含兩個整數(shù)N, M。
第二行包含N＋M＋1個整數(shù)A1,A2, . ,A(N＋M＋1)o
其中，0<=N ,M <=10^5，―10^9<=Ai ≤10^9。

二、解題思路

后綴表達(dá)式求最大其實就是中綴表達(dá)式求最大，但是后綴表達(dá)式無括號，中綴表達(dá)式有括號，所以經(jīng)過括號前面加符號，可以將符號變?yōu)檎枴?/p>

一共有兩種情況：

首先是M=0即沒有減號的情況，這樣只要將所有數(shù)加起來就行了

第二種情況是符號有加有減，這時我們要求最大可以將最大的數(shù)放在括號外面，最小的數(shù)和某些數(shù)放在括號里面（最小的數(shù)要在括號的最前面，保證括號去掉之后最小的數(shù)是減去的，其余數(shù)是加的），然后減去這個括號。其余的正數(shù)加在括號外面，負(fù)數(shù)可以加在括號里，如果加號不夠了，負(fù)數(shù)可以通過減號變成整數(shù)（如果加號不夠負(fù)數(shù)加在括號里面，那么肯定有剩余的減號，反之減號不夠，加號肯定多，最終都能保證負(fù)數(shù)取絕對值之后加上去）。此時最小的數(shù)一定是要被減去的（不管正負(fù)）。

綜合起來第二種情況就是最大的數(shù)要不變的加在表達(dá)式里面，最小的數(shù)一定是減去的。其余數(shù)都可以通過括號或者正數(shù)加，負(fù)數(shù)減操作變?yōu)檎龜?shù)加在表達(dá)式里面，即其余數(shù)取絕對值加起來。

三、完整代碼

四、出現(xiàn)問題

開始的時候沒有想到括號和正負(fù)數(shù)的問題，對后綴表達(dá)式還是不太了解