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