algorithm - 算法分析——有什么想法吗？

Question

可能重复：
至少长度为 L 的最大连续子序列和

令 X = {x1, x2, · · · , xn} 为任意数（正数或负数）的序列。给出一个 O(n) 时间的算法来找到所有连续子序列中总和最大的连续元素 xi,xi+1,···,xj 的子序列。例如，对于 X = {2,5, -10, 3, 12, -2, 10, -7, 5}，{3, 12, -2, 10} 是一个解。

Answer 1

这个问题可以使用动态规划来解决。假设您的输入是数组a，您可以创建一个S相同长度的数组。以下是问题的递归关系。

S[i] = S[i-1] + a[i] > a[i] ? S[i-1] + a[i] : a[i]

基本情况：S[0] = a[0]

保持max跟踪最大总和。最后返回max.

Answer 2

答案是http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm

该算法背后的想法是，我们假设我们知道长度为 N 的数组的问题的真正最大子数组，并且我们知道从任一端开始的最大子数组。（基本原理：如果我们假设我们知道接触末端的最大序列，并且我们逐渐将更多元素添加到末端，那么我们不会错过真正的最大子数组，因为在某些时候添加到末端的元素将是相同的元素作为真正的最大子数组的端点。）添加一个额外的元素可能会增加连接到末尾的最长子数组的长度。如果子数组的总和低于 0，我们将其重置。如果它超过了我们当前对真正最大子阵列的最佳候选解决方案，我们将替换我们的最佳候选解决方案。

或者，我们可以使用集成的力量。（这是一个 O(N) pass 你可以免费做；你也可以免费进行微分。）然后我们查看所有极值，搜索两个极值 MIN 和 MAX，使得 MAX 在 MIN 的右侧（或否则你会找到最负的总和），并且MAX-MIN（连续总和）是最大的。你可以暴力破解这个子问题（如果极端数的数量小于 sqrt(N)，仍然是 O(N)），或者你可以以更有效的方式解决它[可以在这里使用一些帮助]。

Answer 3

这是所有非负元素的序列，很容易在线性O(n)时间内找到。