python - 当第一个数字为负数时，Kadane 算法无法满足条件

Question

我的算法如下所示:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

在此基础上，我编写的代码如下:

def maxSubArraySum(a,size):

    max_so_far = 0
    max_ending_here = 0

    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if max_ending_here < 0:
            max_ending_here = 0

        # Do not compare for all elements. Compare only   
        # when  max_ending_here > 0
        elif (max_so_far < max_ending_here):
            max_so_far = max_ending_here

    return max_so_far

# Driver function to check the above function 
a = [-1,-2,-3,-4]
print ("Maximum contiguous sum is", maxSubArraySum(a,len(a))).

当数组为[-1,-2,-3,-4]时，这段代码以某种方式给我输出0。我当前的代码中有什么需要纠正的地方吗？

Answer 1

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

因此，包含所有负数的列表将使算法出错。但如果你仔细想想，所有负整数列表的最大和只不过是 max(list_of_negative_integers)。

但是，如果您想创建通用解决方案，

• 添加另一个变量max_in_array和一个标志。
• 设置标志
• 循环遍历项目
  • 在循环时使 max_in_array 保持最新。
  • 如果发现正数，则关闭标记。
  • 执行现有逻辑来更新已有的两个变量
• 如果标志关闭，则返回max_so_far，否则返回max_in_array

这里是一个实现供引用:

def max_sub_array_sum(arr):
    max_so_far = max_ending_here = 0
    max_in_arr = arr[0]
    flag = True

    for item in arr:
        if flag:
            max_in_arr = max(max_in_arr, item)

        max_ending_here = max(0, max_ending_here + item)
        max_so_far = max(max_so_far, max_ending_here)

        if item > 0:
            flag = False

    return max_in_arr if flag else max_so_far

另一种没有额外变量的方法:

def max_sub_array_sum(arr):
    max_so_far = curr_max = arr[0]

    for item in arr[1:]:
        curr_max = max(item, curr_max + item)
        max_so_far = max(max_so_far, curr_max)

    return max_so_far