Maximum problem - 推理遊戲

※ 引述《Redsuns (ZZZzzz...)》之銘言：
: 1. 基本題
: 假設有一數列 {X1,X2,X3,X4,.....Xn}
: 請找出一演算法能夠找出一連續的子數列,使他們的和為最大值
: 例: {2,-4,2,5,-2,3,4,-5,3,1} 則其子數列{2,5,-2,3,4}有最大的和
目前想到的方法:

step1
把頭尾的負數去除掉(最大和的數列兩端必不含負數)
ex:{-3,-4,2,5,-2,3,4,-5,3,1}
--> {2,5,-2,3,4,-5,3,1}

step2
把連續的負數或正數相加
(這時首末項是正數, 共有奇數項, 正負間隔出現)
ex:{2,5,-2,3,4,-5,3,1}
--> {7,-2, 7,-5, 4}

step3
比較首尾兩項, 取小者, 將之與相鄰的負數相加
如果小於零就把它從數列中移除,
如果大於零把它跟旁邊的正數(即第三項或倒數第三項)相加

重複step3

ex:{7,-2,7,-5,4}
-->min(7,4)=4
-->{7,-2,7,-1}
^^捨去
-->{7,-2,7}
-->{5,7} (首末二項相等時,取首項或末項沒有關係)
-->{12}

加到最後的答案應該就是那個最大值了
只要在過程中紀錄頭尾兩項相對原始的數列是第幾項即可

--