Re: [問題] 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}
加到最後的答案應該就是那個最大值了
只要在過程中紀錄頭尾兩項相對原始的數列是第幾項即可
--
※ 發信站: 批踢踢實業坊(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)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 5 篇)：
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
17
56
44
76
