LeetCode 53. 最大子序和

题目

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

贪心算法，并记录最大值

class Solution:
    def maxSubArray(self, nums: [int]) -> int:
        #穷举法
        # maxNum = max(nums) #记录最大值
        # tempList = nums
        # # print(tempList)
        # for i in range(len(nums)):
        #     # print("tempList: "+str(tempList[1:]))
        #     # print("nums: "+ str(nums[:-i-1]))
        #     tempList = [a+b for a,b in zip(tempList[1:],nums[:-i-1])]
        #     # print(tempList)
        #     if len(tempList)>0 and maxNum < max(tempList):maxNum = max(tempList)
        #     # print(maxNum)
        # return maxNum
        #贪心算法
        maxLength = len(nums)
        tempList = [nums[0]] #记录临时数组
        maxNum = nums[0]
        for i in range(1, maxLength):
            tempList.append(nums[i])
            if sum(tempList) > nums[i]:#加了当前元素后临时最大量上升就继续添加，否则就重置
                maxNum = max(maxNum, sum(tempList))
            else:
                tempList = [nums[i]]
                maxNum = max(maxNum, nums[i])
        return maxNum