小明是一個有強迫症的盜賊,他盜技精湛屢屢得手。小明害怕自己的後半生在監獄中度過,他打算干完這一票就收手。
在街上現有n座房屋,每個房屋的財富價值為a[i],小明希望在這n個房屋中盜取盡可能多的價值。由於有的房屋存在年久失修等問題小明進入房屋時存在受傷風險,所以財富價值可能為負。由於小明具有強迫症,他每次出手僅會盜取連續的任意房屋,小明至少選取一個房屋進行偷盜。
輸入格式:
第一行一個整數n(1≤n≤1000000);
第二行n個整數表示每個房屋的財富價值ai。
輸出格式:
一行一個整數表示小明能盜取的最大價值。
輸入樣例:
在這裡給出一組輸入。例如:
5
3 4 -1 4 -10
輸出樣例:
在這裡給出相應的輸出。例如:
10
樣例解釋
小明盜取1-4號房屋,價值為3+4+(-1)+4=10