列表排序法
列表排序法
提问于 2015-06-11 11:20:58
所以，我必须找到连续子集的最大和，我在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)
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-06-11 11:30:21
这不是动态规划，它是一个蛮力的解决方案。解决方案似乎是正确的，但正如你所观察到的-它是低效的。
一个O(n)解决方案可以通过应用动态规划来实现，将D(i)表示为以i结尾的最大子连续子数组，并且必须包括i。
D(-1) = 0
D(i) = max{ arr[i], D(i-1)这样做的想法是，您有两个选择--获得以i-1结尾的“最佳”数组并将元素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]给出(按照上面的数组，然后返回)
Stack Overflow用户
发布于 2015-06-11 11:40:52
基本上是再次计算和，again.You可以通过将和存储在数组中来避免这种情况。你可以用O(n)来做。
设S0，1.n-1是序列设T0,1，.n-1是从i元开始的最大连续和。
现在要填充Ti，从相反开始。Tn-1=最大值(Sn-1，0)
现在Ti=max(Ti+1+Si，Si ,0)
现在，遍历'T‘数组，找到最大和。
设Tm为最大值。
计算从Sm开始的精确序列，并将所有元素加到和等于Tm为止
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30779358
复制相关文章
相似问题
腾讯云开发者
