作者citronrisky (瑞士基)
看板Inference
標題Re: [問題] Maximum problem
時間Thu Nov 18 05:18:16 2004
※ 引述《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}
加到最後的答案應該就是那個最大值了
只要在過程中紀錄頭尾兩項相對原始的數列是第幾項即可
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.75.239.100
※ 編輯: citronrisky 來自: 211.75.239.100 (11/18 15:05)
※ 編輯: citronrisky 來自: 211.75.239.100 (11/18 15:11)