53. 最大子数组和

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

• 子数组是数组中的一个连续部分。

1. 动态规划

• 思路:
  1. 遍历数组中的每个元素
  2. 对于每个元素，判断当前的子数组是否应该包括这个元素：如果 cur_sum + num 小于 num，那么就从当前元素重新开始计算子数组和
  3. 否则，继续累加当前元素到 current_sum，在每一步更新全局最大和 max_sum

class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""cur_sum = nums[0]max_sum = nums[0]for num in nums[1:]:cur_sum = max(num, cur_sum + num)# 更新当前最大和max_sum = max(max_sum, cur_sum)# 更新全局最大和return max_sum

• 时间复杂度: O(n)
• 空间复杂度: O(1)

2. 分治法

• 分治法将数组分成两个子数组，分别求出左边和右边的最大子数组和，然后再计算跨越中点的最大子数组和，最后取这三者中的最大值

• 具体步骤：

  1. 将数组分为两部分，递归求解每一部分的最大子数组和
  2. 计算跨越中点的子数组和（即左边的部分和右边的部分结合）
  3. 返回三个值中的最大值

def maxSubArray(nums):def divide_and_conquer(nums, left, right):if left == right:return nums[left]mid = (left + right) // 2left_sum = divide_and_conquer(nums, left, mid)right_sum = divide_and_conquer(nums, mid + 1, right)# 计算跨越中点的最大子数组和cross_sum = find_cross_sum(nums, left, right, mid)return max(left_sum, right_sum, cross_sum)def find_cross_sum(nums, left, right, mid):left_max = float('-inf')right_max = float('-inf')current_sum = 0for i in range(mid, left - 1, -1):current_sum += nums[i]left_max = max(left_max, current_sum)current_sum = 0for i in range(mid + 1, right + 1):current_sum += nums[i]right_max = max(right_max, current_sum)return left_max + right_maxreturn divide_and_conquer(nums, 0, len(nums) - 1)

• 时间复杂度: O(logn)

• 空间复杂度: O(logn)

• 3. 暴力枚举

• 思路是遍历所有的连续子数组，计算它们的和，并找出最大和

• 这个方法虽然直观，但对于大数组来说效率较低

def maxSubArray(nums):max_sum = float('-inf')n = len(nums)for i in range(n):cur_sum = 0for j in range(i, n):cur_sum += nums[j]max_sum = max(max_sum, cur_sum)return max_sum

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)