『贪心算法』最大子序和53

题目相关

• 原题链接：53. 最大子序和 - 力扣（LeetCode）
• 涉及知识：贪心算法
• 题目难度：★

题目解读

根据分析，该题符合最优子结构的性质，即可以通过贪心选择将问题不断拆分成子问题，并通过子问题的最优解推出最终问题的最优解。因为最大子序和可以通过不断地比较当前子序和和先前最大子序和比较而更新产生。

Python相关

无

具体实现

自己实现的很直观的版本：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        temp = nums[0]
        for num in nums[1:]:
            if temp < 0:
                temp = num
            else:
                temp += num
            if temp > res:
                res = temp
        return res

相比而言，一种更加pythonic的实现：

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

相比而言，一种更加Pythonic的实现：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = temp = nums[0]
        for num in nums[1:]:
            temp = max(num, temp + num)
            res = max(temp, res)
        return res