列出后续方法

Question

所以，我必须找到连续子集的最大总和，我在python中遵循了这个算法。

def SubSeq(list):
    final_list = None
    suming = 0
    for start in range(len(list)):
        for end in range(start+1, len(list)+1):
            subseq = list[start:end]
            summation= sum(list[start:end])
            if summation > suming:
                suming = summation
                final_list = subseq
    return final_list


print SubSeq([5, 15, -30, 10, -5, 40, 10])

虽然运行时间是 O(n^2)，但我想知道这是否是动态规划中的正确方法。另外，有没有办法让它成为 O(n)

Answer 1

这不是动态规划，它是一种蛮力解决方案。该解决方案似乎是正确的，但作为您的观察者 - 它效率低下。

一个O(n)的解决方案可以通过应用动态规划来实现，表示D(i)作为以i结尾的最大子连续子数组，并且必须包括i。

D(-1) = 0
D(i) = max{ arr[i], D(i-1)

想法是，您有两个选择 - 获取以 i-1 结尾的先前 "best" 数组并向其添加元素 i，或者创建一个以 i 开头的新数组i.

最后，通过在DP解决方案中应用上述内容，您将得到一个数组，其中每个元素表示以该索引结尾的最大子连续数组，您所要做的就是从该数组中选择最大值得到最大和的值，然后返回数组得到实际的子序列。

示例：

array = 5,15,-30,10,-5,40,10

应用动态规划：

D(-1) = 0
D(0) = 5
D(1) = 20
D(2) = -10
D(3) 10 //because max{-10+10,10} = 10
D(4) = 5
D(5) = 45
D(6) = 55

现在你有了数组：

D = [5,20,-10,10,5,45,55]

最大子序列的值为 55，由 [10,-5,40,10] 给出（按照上面的数组，然后返回）

Answer 2

您基本上是在再次计算总和，again.You 可以通过将总和存储在数组中来避免这种情况。您可以在 O(n) 中完成。

设S[0,1..n-1]为序列设 T[0,1,...n-1] 为数组，其中 T[i] 是从第 i 个元素开始可能的最大连续和。

现在填充T[i]，从反方向开始。 T[n-1]=max(S[n-1],0)
现在 T[i]=max(T[i+1]+S[i] , S[i] ,0)

现在遍历 'T' 数组以找到最大总和。

设T[m]为最大值。

要计算确切的序列，从S[m]开始，将所有元素相加，直到总和等于T[m]

列出后续方法

List Subsequents Method

algorithm

discrete-mathematics