最大连续子序列

Question

大家好,请帮助以下算法,

假设我们有序列(负号允许)4,3,-2,13,11,1,1,8,5我需要找到子序列与部件之间最大总和,而且成员之间的距离应为4至少在原始序列.例如子序列将是(13,8)= 21

感谢帮助.

Answer 1

编辑:

因此,您需要最大总和子序列,以便任何两个元素i和j所选子序列中都有j - i >= 4.我们可以用动态编程解决这个问题.

让我们a成为给定的数组.

我们m[i] = maximum sum subsequence with the desired properties ending at position i.

如果我们有

    1  2   3   4   5  6  7  8  9  
a = 4, 3, -2, 13, 11, 1, 1, 8, 5

然后

m[1] = 4 
m[2] = 3
m[3] = -2
m[4] = 13
m[5] = max(m[5 - 4 = 1] + 11, 11) = max(4 + 11, 11) = 15
...

一般来说,我们有 m[i] = max{max(m[j] + a[i], a[i]), j = 1 to i - 4}

这将是O(n^2).您可以O(n)很容易地从中获得解决方案.请注意,m[j]在上述重复中选择最大值总是有帮助的.因此,计算m遍历它时的最大值,如下面的伪代码:

maxm = -inf
for i = 1 to a.Length do
    m[i] = a[i]

    if (i >= 4 + 1)
        if (m[i - 4] > maxm)
            maxm = m[i - 4]

        m[i] = max(m[i], maxm + a[i])


output the maximum value in `m`.

您可以轻松地将其概括为k代替4.

这不是你想要的,但我还是要离开它,因为我认为这是一个经典问题的有趣变化.

如果你确实在寻找至少有长度的最大和子序列k,那么这个算法将解决这个问题O(n):

让我们a成为你的数字.我们s[i] = s[i - 1] + a[i].这是一个称为前缀和数组.我们可以用它来找到这样的任何序列的总和[i, j]:sum[i, j] = s[j] - s[i - 1].

因此,对于每一个i >= k,我们需要一个j <= i - k + 1这样s[j - 1]最小.拿最后给出最大金额的那个.

s[0] = 0
for i = 1 to a.Length do
    s[i] = s[i - 1] + a[i]

max = -inf
min = inf

for i = k to a.Length do
    if (s[i - k] < min)
        min = s[i - k]
    if (s[i] - min > max)
        max = s[i] - min