python最大子序和

“”"
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
“”"
class Solution:
def maxSubArray1(self, nums):
max_value = nums[0]
temp = []
for i in range(len(nums)):
for j in range(i,len(nums)):
sub_sum = sum(nums[i:j+1])
if sub_sum>max_value:
max_value = sub_sum
return max_value

def maxSubArray2(self, nums):
    size = len(nums)
    if size == 0:
        return 0
    # 以索引 i 结尾的最大子数组的和
    end_i_max = nums[0]
    res = nums[0]
    for i in range(1, size):
        # 例：[-3,1]
        end_i_max = max(nums[i], end_i_max + nums[i])
        res = max(res, end_i_max)
    return res

def maxSubArray3(self, nums):
    sum = 0
    MaxSum = nums[0]
    for i in range(0,len(nums)):
        sum += nums[i]
        if sum > MaxSum:
            MaxSum = sum
        if sum < 0:
            sum = 0
    return MaxSum

L = [-64,78,56,10,-8,26,-18,47,-31,75,89,13,48,-19,-69,36,-39,55,-5,-4,-15,-37,-27,-8,-5,35,-51,83,21,-47,46,33,-91]
s = Solution()
print(s.maxSubArray1(L))
print(s.maxSubArray2(L))
print(s.maxSubArray3(L))