Re: [問題] 一題很像LCS的演算法問題
※ 引述《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
推
05/27 10:34, , 1F
05/27 10:34, 1F
推
06/11 01:45, , 2F
06/11 01:45, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
