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

本文概述

• python
• 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

如果我们将max_so_far与max_ending_here进行比较, 则仅当max_ending_here大于0时, 才能进一步优化上述程序。

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

请参考完整的文章最大总和连续子数组更多细节！