最大和连续子数组的Python程序

python

``````# Python program to find maximum contiguous subarray

# Function to find the maximum contiguous subarray
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

# Driver function to check the above function
a = [ - 13 , - 3 , - 25 , - 20 , - 3 , - 16 , - 23 , - 12 , - 5 , - 22 , - 15 , - 4 , - 7 ]
print "Maximum contiguous sum is" , maxSubArraySum(a, len (a))

# This code is contributed by _Devesh Agrawal_``````

``Maximum contiguous sum is -3``

python

``````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``````