Understanding/implementing最大子数组的枚举解
Understanding/implementing this enumeration solution for maximum subarray
[这是作业。我不是要代码代码,但我可能需要伪代码才能真正掌握这一点。]
对于我的算法 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 的最终迭代。
好的,所以我们知道我们可以对整个列表进行求和。求和有一个基本情况,这个是 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
。
[这是作业。我不是要代码代码,但我可能需要伪代码才能真正掌握这一点。]
对于我的算法 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 的最终迭代。
好的,所以我们知道我们可以对整个列表进行求和。求和有一个基本情况,这个是 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
。