※ 引述《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