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))).

当. output 0_ array is [-1,-2,-3,-4]在我当前的代码中我应该纠正什么吗？

Answer 1

Kadane 算法的简单想法是查找数组的所有正连续段（max_ending_here 用于此）。并跟踪所有正段之间的最大和连续段（max_so_far 用于此）。

因此，包含所有负数的列表将使算法跳闸。但是，如果您考虑一下，所有负整数列表的最大总和不过是max(list_of_negative_integers).

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

• 添加另一个变量max_in_array和一个flag.
• 设置标志
• 遍历项目
  • 循环时保持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

Answer 2

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]))

Answer 3

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

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