推 FRAXIS:Maximum consecutive subsequence 05/27 10:34
推 cai7773:第一個假設 要的時間複雜度沒考慮喔 06/11 01:45
※ 引述《mqazz1 (無法顯示)》之銘言：
: Given a sequence of n numbers,
: find the longest continuous subsequence that has the largest sum.
: algorithm must be less than O(n^2)
: 這一整個數列可能是 10, -1, 900, 12, -35...
: 找出一段讓它的總和最大
: 時間在O(n^2)
: 請問這題是問LCS嗎?
: 還是什麼其它的方法?
可能可以這樣做:
對於任意 i>=1,
假設我們知道從第 1 到第 i 個數當中哪一個開始加, 加到第 i 個數 (包含第 i 個
數) 時, 可達最大總和, 且知道最大總和是多少,
那麼要從第 1 到第 i+1 個數當中任一個數開始加, 加到第 i+1 個數 (包含第 i+1 個
數), 使總和最大的方法只有兩種可能:
(一) 以總和最大的方法從某個數加到第 i 個數, 然後取第 i+1 個數
(二) 只取第 i+1 個數
比較 (一) (二) 兩種總和究竟誰大, 就可以知道要從哪個數開始加, 才能最大化加到第
i+1 個數的總和, 且我們也可算出這個最大總和是多少... in O(1) time! --- 當然我們
是假設每次做加法都是 O(1) time.
用同樣的方法, 我們可以知道究竟要從哪個數開始加, 才能最大化加到第 i+2 個數的總
和...
以上方法從 i=1 開始反覆地做, 就可以解決這題了, 時間是 O(n).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.105.140