53. 最大子序和

题目

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

示例:

  1. 输入: [-2,1,-3,4,-1,2,1,-5,4],
  2. 输出: 6
  3. 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

代码

动态规划题解

  • 一个连续子数组肯定是以数组中的一个数作为结尾。
  • 因此可以通过动态规划，遍历nums数组，求出以每个数为结尾的连续子数组的最大和（存入数组max_end_idx_sum）。
  • 再遍历数组max_end_idx_sum，取最大值，即为nums数组的最大子序和。 ``` max_end_idx_sum[i]: 表示以nums[i]结尾的连续子数组的最大和

初始化 max_end_idx_sum[0] = nums[0], if数组非空 状态转移方程 max_end_idx_sum[i] = max_end_idx_sum[i-1] + nums[i], if max_end_idx_sum[i-1] >= 0 = nums[i], if max_end_idx_sum[i-1] < 0

![image.png](https://cdn.nlark.com/yuque/0/2020/png/1324638/1595254296094-89d7e625-0607-49e2-b157-f0f258857064.png#align=left&display=inline&height=354&margin=%5Bobject%20Object%5D&name=image.png&originHeight=354&originWidth=1139&size=142823&status=done&style=none&width=1139)<br />代码
```python
def maxSubArray(nums):
    if len(nums) < 1:   # 若数组为空
        return 0

    # 求以nums[idx]为结尾的连续子数组的最大和
    max_end_idx_sum = [0] * len(nums)
    max_end_idx_sum[0] = nums[0]
    for idx in range(1, len(nums)):
        if max_end_idx_sum[idx - 1] < 0:
            max_end_idx_sum[idx] = nums[idx]
        else:
            max_end_idx_sum[idx] = max_end_idx_sum[idx - 1] + nums[idx]

    # 从max_end_idx_sum数组中选取最大的元素即为nums数组的最大子序和
    max_sum = max_end_idx_sum[0]
    for idx in range(1, len(max_end_idx_sum)):
        if max_end_idx_sum[idx] > max_sum:
            max_sum = max_end_idx_sum[idx]
    # 或直接 return max(max_end_idx_sum)

    return max_sum

分治法题解