【LeetCode】53.最大子数组和

**最大子数组和**
================**问题描述**
------------给定一个整数数组 `nums`，找到其中最大的连续子数组的和。

**示例1:**

* 输入:`nums = [-2,1,-3,4,-1,2,1,-5,4]`
* 输出:`6`

**示例2:**

* 输入:`nums = [1]`
* 输出:`1`

**示例3:**

* 输入:`nums = [0]`
* 输出:`0`

**解决方案**
------------### 动态规划法我们可以使用动态规划来解决这个问题。动态规划是一种通过分解大问题为小问题的方法，求出每个子问题的最优解，然后组合这些解以得出原问题的最优解。

#### 思路1. 初始化一个数组 `dp`，其中 `dp[i]` 表示从第 `i` 个元素开始的最大连续子数组和。
2. 遍历数组 `nums`，对于每个元素 `nums[i]`，计算其与前面的最大连续子数组和的最大值，并更新 `dp[i]`。

####代码

class Solution:
 def maxSubArray(self, nums: List[int]) -> int:
 # 初始化动态规划数组 dp = [0] * len(nums)
 # 初始化最大子数组和 max_sum = float('-inf')
 # 遍历数组，计算每个元素的最大连续子数组和 for i in range(len(nums)):
 if i ==0:
 dp[i] = nums[i]
 else:
 dp[i] = max(dp[i-1]+nums[i], nums[i])
 # 更新最大子数组和 max_sum = max(max_sum, dp[i])
 return max_sum

### Kadane算法Kadane算法是一种线性时间复杂度的算法，用于求解最大子数组和问题。

#### 思路1. 初始化一个变量 `max_sum`，用来存储当前最大子数组和。
2. 遍历数组 `nums`，对于每个元素 `nums[i]`，计算其与前面的最大连续子数组和的最大值，并更新 `max_sum`。

####代码

class Solution:
 def maxSubArray(self, nums: List[int]) -> int:
 # 初始化最大子数组和 max_sum = float('-inf')
 # 遍历数组，计算每个元素的最大连续子数组和 for i in range(len(nums)):
 if i ==0:
 current_sum = nums[i]
 else:
 current_sum = max(current_sum+nums[i], nums[i])
 # 更新最大子数组和 max_sum = max(max_sum, current_sum)
 return max_sum

### 分治法分治法是一种递归的算法，用于求解最大子数组和问题。

#### 思路1. 初始化一个变量 `max_sum`，用来存储当前最大子数组和。
2. 将数组 `nums` 分成两半，分别计算左半部分和右半部分的最大连续子数组和。
3. 更新 `max_sum` 为左右两半部分中最大的值。

####代码

class Solution:
 def maxSubArray(self, nums: List[int]) -> int:
 # 初始化最大子数组和 max_sum = float('-inf')
 # 递归计算左半部分和右半部分的最大连续子数组和 def recursive_max_subarray(left, right):
 nonlocal max_sum if left == right:
 return nums[left]
 mid = (left + right) //2 left_max = recursive_max_subarray(left, mid)
 right_max = recursive_max_subarray(mid+1, right)
 # 更新最大子数组和 max_sum = max(max_sum, left_max, right_max)
 return max(left_max, right_max)
 recursive_max_subarray(0, len(nums)-1)
 return max_sum

### 总结以上是对最大子数组和问题的解决方案总结。动态规划法、Kadane算法和分治法都是有效的方法，分别具有不同的时间复杂度和空间复杂度。