递归，分而治之最大子数组

Question

我似乎无法弄清楚为什么我在编译时收到一条针对下面突出显示的行的错误消息。错误消息是 "ValueError: need more than 2 values to unpack"... 在此先感谢您的帮助

def divConHelper(array, first, center, last):
    sumRight = float('-inf') #assign impossibly low number
    sumLeft = float('-inf') #assign impossibly low number
    leftIndexMax = 0
    rightIndexMax = 0 

    # Determine crossover max toward left
    currentLTotal = 0
    for i in range(first, center): 
    #Incrementally add values to sum
      currentLTotal += sum(array[i:center-1])
    #if the total is greater than the sumLeft, replace
      if currentLTotal > sumLeft:
        sumLeft = currentLTotal   
        leftIndexMax = i 

  # Determine crossover max toward right
    currentRTotal=0
    for i in range(center+1, last):
    #Incrementally add values to sum
      currentRTotal += sum(array[center:i+1])
    #if the rightTotal is greater than the sumRight, replace
      if currentRTotal > sumRight:
        sumRight = currentRTotal
        rightIndexMax = i+1 

    bothTotal = sumRight + sumLeft

    return(leftIndexMax, rightIndexMax, bothTotal)
    #return(bothTotal)

def divConMaxSub(self, array, first, last):

    if (last-first) == 0: 
      return array[first: last +1], array[0]


    center = (first+last)// 2
    #Recursive calls to divConMaxSub
    (minA, maxA, sumA) = self.divConMaxSub(array, first, center)
    (minB, maxB, sumB) = self.divConMaxSub(array, center+1, last)
    #call to get max cross values
    (maxL, maxR, maxCross) = divConHelper(array, first, center, last)

    #Calulate the max subarray value
    finalMax = max(sumA, sumB, maxCross)
    #Logic block for return values
    if (finalMax == sumA):
      return array[minA: maxA], sumA
      #return minA, maxA, sumA
    elif (finalMax == sumB):
      return array[minB: maxB], sumB
      #return minB, maxB, sumB
    elif (finalMax == maxCross):
      return array[maxL: maxR], maxCross
      #return maxL, maxR, maxCross

这是我的主要代码

    from array import *
from utilities import utilities
from algorithms import algorithms  
def main():
   utils = utilities()
   alg = algorithms()
   results = utils.load()
   for line in results:
     max_sub_array, max_sum = alg.simpleenumeration(line)
     utils.printtofile("Simple Enumeration", max_sub_array, max_sum)
     max_sub_array, max_sum = alg.betterenumeration(line)
     utils.printtofile("Better Enumeration", max_sub_array, max_sum)
     max_sub_array, max_sum = alg.divConMaxSub(line)
     utils.printtofile("Divide and Conquer", max_sub_array, max_sum)
     max_sub_array, max_sum = alg.linear_sub_array(line)
     utils.printtofile("Linear sub array", max_sub_array, max_sum)
   #    print("--------------------")

main()

Answer 1

这条语句：

return array[minA: maxA], sumA

不 return 三个参数（正如您在此代码中所期望的那样）：

(minA, maxA, sumA) = self.divConMaxSub(array, first, center)

它 return 将数组的一部分作为第一个参数，将总和作为第二个参数。因此，Python报错不能用divConMaxSub的输出来初始化左边的三个值，因为右边只有两个值。

递归，分而治之最大子数组

Recursive, Divide and Conquer Max Subarray

python

recursion

divide-and-conquer