Understanding/implementing最大子数组的枚举解

Question

[这是作业。我不是要代码代码，但我可能需要伪代码才能真正掌握这一点。]

对于我的算法 class，我们正在处理最大子数组问题。我已经实现了 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)

这是我的教授提供的规格：

Algorithm 1: Enumeration. Loop over each pair of indices i, j and compute the sum ∑= []. Keep the best sum you have found so far.

Algorithm 2: Better Enumeration. Notice that in the previous algorithm the same sum is computed many times. In particular, notice that ∑ = [] can be computed from ∑−1 = [] in O(1) time, rather than starting from scratch. Write a new version of the first algorithm that takes advantage of this observation.

在这一点上，我明白一旦我有了 i:j 的总和，我可以使用 current_sum 更快地计算 i:j+1。我认为对我来说症结所在是：

我不确定我应该从什么时候开始计算 current_sum - 即 i:j- 以及什么时候我应该依靠 current_sum 来计算 i:j+1.
如何有时只计算 i:j，留下 i:j+1 来计算大多数值？
如何防止 i:j+1 溢出数字列表？

更新：

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 的最终迭代。

Answer 1

好的，所以我们知道我们可以对整个列表进行求和。求和有一个基本情况，这个是 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。

Understanding/implementing最大子数组的枚举解

Understanding/implementing this enumeration solution for maximum subarray

algorithm

python-2.6