使用 kadane 算法到 return 子数组以及子数组的最大和

Question

我的这段代码 returns 使用 kadane 算法的子数组的最大和。我可以对这段代码做哪些更改，以 return 对应于最大总和的子数组？

def maxSubArray(a,size):
    curr_max=a[0]
    max_so_far=a[0]
    
    for i in a[1:]:
        curr_max=max(a[i],curr_max+a[i])
        max_so_far=max(max_so_far,curr_max)
    return max_so_far
a = [-2, -3, 4, -8, -2, 1, 5, -3] 
maxSubArraySum(a,len(a))

Answer 1

这是一个计算最大和和相应的连续子数组的解决方案。它使用带有 i 的单个 for 循环。然后 j 落后于 i 并且有条件地前进。 j 和 i 帮助设置到目前为止提供最大和的子数组的开始和结束索引。最后，开始和结束索引用于对数组和 return 子数组进行切片。

def maxSubArraySum(a):
    max_so_far = 0
    current_max = 0
    start_index = 0
    end_index = 0
    j = 0 #trails i in the following loop. i and j help set start and end indexes

    for i in range(len(a)):
        current_max += a[i]

        if current_max > max_so_far:
            max_so_far = current_max
            start_index = j
            end_index = i

        # reset current max if negative and advance j
        if current_max < 0:
            current_max = 0
            j = i + 1

    result_array = a[start_index: end_index+1]
    print(f"Max sum is {max_so_far} for contiguous subarray: {result_array}")

maxSubArraySum([-2, -3, 4, -8, -2, 1, 5, -3])

#Output: Max sum is 6 for contiguous subarray: [1, 5]

使用 kadane 算法到 return 子数组以及子数组的最大和

To return subarray as well alongside maximum sum of subarray using kadane's algorithm

python

arrays

sub-array