当第一个数字为负数时，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))).

这段代码以某种方式在 array is [-1,-2,-3,-4] 时给了我 output 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 和一个 flag。
设置标志
遍历项目
- 在循环时保持 max_in_array 最新。
- 如果找到正数，则关闭标志。
- 执行现有逻辑来更新您已有的两个变量
如果标志关闭，return 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

Answer 2

只需反转 if 语句 - 在更新数组之前检查 max。

if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 
if (max_ending_here < 0) 
                max_ending_here = 0;

Answer 3

Python 以使用 3.0 解决方案的更短和可读的代码而闻名，这可能对您有所帮助。要更好地理解算法，请观看此视频：- https://www.youtube.com/watch?v=2MmGzdiKR9Y

def max_sub_array_sum(arr):

    kadance=[]
    #kadance[i]=arr[0]
    kadance.append(arr[0])

    for i in range(1,len(arr)):
        #kadance[i] = max(kadance[i-1]+arr[i],arr[i])
        temp = max(kadance[i-1]+arr[i],arr[i])
        kadance.append(temp)

    ans = kadance[0]

    for i in range(1,len(kadance)):
        ans = max(ans,kadance[i])

    return ans

print(max_sub_array_sum([-1,-2,-3,-4]))

当第一个数字为负数时，Kadane 的算法不满足条件

Kadane's algorithm fails to satify the condition when first number is negative

python

kadanes-algorithm