Leetcode刷题记录24——最大子数组和

题源：https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked

题目描述：

思路一：
使用经典的动态规划算法——Kadane 算法。

• 初始化变量：
  • max_sum：用于记录当前找到的最大子数组和。
  • current_sum：用于记录当前子数组的和。
• 从第二个元素开始遍历数组：
  • 对于每个元素，更新 current_sum 为 current_sum + nums[i] 和 nums[i] 中的较大值。
  • 更新 max_sum 为 current_sum 和 max_sum 中的较大值。
• 返回 max_sum。
• 具体来说，对于数组中的每个元素，Kadane算法都会做出以下决策：
  • 如果把当前元素加入现有的子数组中（即当前元素加上current_sum），是否会形成一个更大的子数组和？如果是，则更新current_sum为current_sum + num。
  • 如果不是，那么就从当前元素重新开始一个新的子数组，因为单凭当前元素就能构成目前为止最大的子数组和。

代码实现如下：

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""max_sum = nums[0]current_sum = nums[0]for i in range(1, len(nums)):current_sum = max(nums[i], nums[i]+current_sum)max_sum = max(max_sum, current_sum)return max_sum

执行时间如下：