---

highlight: xcode theme: channing-cyan

---

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第15天，点击查看活动详情 。如果哪里写的不对，请大家评论批评。

最大子数组和

题目

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

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

示例 1

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

示例 2：

js 输入：nums = [1] 输出：1

示例 3：

js 输入：nums = [5,4,-1,7,8] 输出：23

分析

动态规划

1. 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2. 动态规划可以通过填表的方式来逐步推进，得到最优解.

图解

1. 定义dp数组： ```js
2. dp[i]表示nums中以nums[i]结尾的最大子序和。
3. dp[i]中最大的元素即为nums的最大子序和。
4. dp[0] = nums[0] ```
5. 可以得到公式 $$ dp[i]=max(dp[i−1]+nums[i],nums[i]) $$
6. 第一步，初始化一个新的数组来存储[i]结尾的最大子序和var dp = Array(repeating: 0, count: nums.count)
7. dp[0]存放nums[0]作为单个子序时的和，可以减少一次循环，dp[0] = nums[0]
8. 定义最大子序和max_num，暂时存储nums[0]的数组，也可以防止数组只有一位数据

9. 开始循环，进入图解

10. 第一步循环：取值为1，dp[1] = max(dp[0] + nums[1],nums[1])转换一下dp[1] = max(-2 + 1,1) = 1，max_num = max(-2, 1) = 1

11. 第二步循环：取值为-3，dp[2] = max(dp[1] + nums[2],nums[2])转换一下dp[2] = max(1 -3,-3) = -2，max_num = max(1, -2) = 1

12. 第三步循环：取值为4，dp[3] = max(dp[2] + nums[3],nums[3])转换一下dp[3] = max(-2 + 4,4) = 4，max_num = max(1, 4) = 4

13. 第四步循环：取值为-1，dp[4] = max(dp[3] + nums[4],nums[4])转换一下dp[4] = max(4+-1,-1) = 3，max_num = max(4, 3) = 4

14. 第五步循环：取值为2，dp[5] = max(dp[4] + nums[5],nums[5])转换一下dp[5] = max(3+2,2) = 5，max_num = max(4, 5) = 5

15. 第六步循环：取值为1，dp[6] = max(dp[5] + nums[6],nums[6])转换一下dp[6] = max(5+1,1) = 6，max_num = max(5, 6) = 6

16. 第七步循环：取值为-5，dp[7] = max(dp[6] + nums[7],nums[7])转换一下dp[7] = max(6 - 5, -5) = 1，max_num = max(6, 1) = 6

17. 第八步循环：取值为4，dp[8] = max(dp[7] + nums[8],nums[8])转换一下dp[8] = max(1+4, 1) = 5，max_num = max(6, 5) = 6

代码

```js

class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count > 0 else { return Int.min } var dp = Array(repeating: 0, count: nums.count) dp[0] = nums[0] var max_num = res[0] for i in 1..<nums.count { dp[i] = max(dp[i - 1] + nums[i],nums[i]) max_num = max(max_num, dp[i]) } return max_num } } ```