leetcode-53 最大子序和 python3 贪心解法

解题思路：
记录当前元素nums[i],当前序列的最大值result_temp,总的最大值result
1.如果元素全为负数，则选出最大的负数，并返回。
2.如果元素内有正数也有负数，则：
1. 如果遇到负数，有两种情况。第一种，此负数对当前序列最大值可能有贡献，例如：2，-1，3.此时保留该负数。如果，当前子序列的和result_temp+负数>0（当后面的数为正数时，该负数可以保留），将result_temp更新为result_temp+该负数。第二种，比如：2，-3，4.此时，该负数不可能对当前的子序列有贡献，舍弃该负数，并将result_temp更新为0，计算下一个子序列的和。
2. 如果遇到正数，则当前子序列和一定会变大。此时更新reuslt_temp += 该正数，更新result为result_temp。
3. 返回最终的最大值result.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return
        if len(nums) == 1:
            return nums[0]
        result = nums[0] 
        result_temp = nums[0]
        for i in range(1,len(nums)):
            if nums[i] < 0 :
                if result < 0:
                    if nums[i] > result:
                        result = nums[i]
                        continue
                if nums[i] +result_temp <= 0:
                    result_temp = 0
                    continue
                else:
                    result_temp += nums[i]
                    if result_temp > result:
                        result = result_temp
            else:
                if result < 0:
                    result = 0
                    result_temp = 0
                result_temp += nums[i]
                if result_temp > result:
                    result = result_temp
        return result

时间复杂度O(n),空间复杂度O(1)

我的方法看起来比较复杂，看到官方的方法写的更为简洁，不过思想是差不多的。

官方方法：

class Solution:
    def maxSubArray(self, nums: 'List[int]') -> 'int':
        n = len(nums)
        curr_sum = max_sum = nums[0]

        for i in range(1, n):
            curr_sum = max(nums[i], curr_sum + nums[i])
            max_sum = max(max_sum, curr_sum)
            
        return max_sum