了解/实施此枚举解决方案的最大子阵列

[这是作业。我不是要求代码，但我可能需要伪代码才能真正掌握这一点。]了解/实施此枚举解决方案的最大子阵列

对于我的算法类，我们正在研究最大的子数组问题。我已经实现Kadane的线性解决方案，以及下面的简单枚举：

def better_enumeration(Array): 
    max_subset_sum = current_sum = 0 
    start_subset_index = stop_subset_index = 0 

    for i in range(0, len(Array)+1): 
     for j in range(i, len(Array)+1): 
      current_sum = sum(Array[i:j]) 

      if current_sum > max_subset_sum: 
       max_subset_sum = current_sum 
       start_subset_index = i 
       stop_subset_index = j 
    return (Array[start_subset_index:stop_subset_index], max_subset_sum)

这里是我的教授已经提供的规格：

算法1：枚举。循环每对索引i，j并计算总和Σ= []。保持迄今为止找到的最好的总和。

算法2：更好的枚举。注意，在前面的算法中，多次计算相同的和。尤其要注意的是Σ= []可以从O（1）时间的Σ-1 = []计算出来，而不是从头开始计算。写一个利用这个观察结果的第一个算法的新版本。

在这一点上，我明白，一旦我有i：j的总和，我可以使用current_sum计算i：j + 1。对我来说，症结点，我相信是：

我不知道在哪点，我应该开始计算current_sum，也就是说，我：J-当我应该依靠current_sum计算我：J- +1。
我该如何计算i：j有时候离开i：j + 1来计算大多数值？
如何防止i：j + 1溢出数字列表？

UPDATE：

def better_enumeration(Array): 
max_subset_sum = current_sum = 0 
start_subset_index = stop_subset_index = 0 

for i in range(0, len(Array)+1): 
    current_sum = 0 

    for j in range(i, len(Array)+1): 
     current_sum += Array[j] 

     if current_sum > max_subset_sum: 
      max_subset_sum = current_sum 
      start_subset_index = i 
      stop_subset_index = j 

return (Array[start_subset_index:stop_subset_index], max_subset_sum)

现在我只需要弄清楚如何不溢出j的最后一次迭代。

来源

2015-10-17 Lithedreamer

我建议你参考这个[资源]（http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/）。此外，我敢肯定，如果你尝试，你将能够操纵代码来检索具有最大连续总和的子阵列。 –

感谢您的链接，拉胡尔。它看起来像我的Kadane算法的实现，这对我来说很容易理解。我只是不会在枚举上获得这种改进。 – Lithedreamer

好的，所以我们知道我们可以通过整个列表创建一个总和。总结有一个基本情况，但这是0.

for i in range(0, len(Array)+1): 
    current_sum = 0

因此，0进入外部循环。

for j in range(i, len(Array)+1): 
    current_sum += Array[j]

你需要知道的下一件事是Python的range函数循环range(x, y-1)。我们在这里溢出了这个清单。如果我们不溢出这个列表，那么我们仍然得到一个精确的总和，但是我们失去了最大子集中的最后一个整数。

if current_sum > max_subset_sum: 
    max_subset_sum = current_sum 
    start_subset_index = i 
    stop_subset_index = j

一旦我们理解了range作品，到j一个简单的打印循环如何，表明我们其实也枚举过程中遇到的全部子集：

print 'Loop ' + str(j) + ': ' + str(Array[i:j])

因此，我们的最后一个问题是stop_subset_index应等于j+1。

来源

2015-10-17 20:32:58 Lithedreamer

了解/实施此枚举解决方案的最大子阵列

回答

相关问题