求子数组的最大和

Question

给定一个由N个整数组成的数组arr。查找具有最大和的连续子数组。

输入：N=5arr[]=｛1,2,3，-2,5｝输出：9说明：最大子阵列和为9元素(1，2，3，-2，5(是一个连续的子数组。

Answer 1

签出此代码：

from sys import maxint
def maxSubArraySum(a,size):

max_so_far = -maxint - 1
max_ending_here = 0

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

为了更好地理解，请查看以下解释：Kadane算法