携手创造，共同生长！这是我参加「日新计划 8 月更文挑战」的第15天，点击检查活动详情。假如哪里写的不对，请我们谈论批评。

最大子数组和

题目

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

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

示例 1

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

示例 2：

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

示例 3：

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

剖析

动态规划

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

图解

1. 定义dp数组：

- dp[i]表示nums中以nums[i]结束的最大子序和。
- dp[i]中最大的元素即为nums的最大子序和。
- dp[0] = nums[0]

2. 能够得到公式

3. 第一步，初始化一个新的数组来存储[i]结束的最大子序和var dp = Array(repeating: 0, count: nums.count)

4. dp[0]寄存nums[0]作为单个子序时的和，能够减少一次循环，dp[0] = nums[0]

5. 定义最大子序和max_num，暂时存储nums[0]的数组，也能够避免数组只要一位数据

6. 开端循环，进入图解

   

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

   

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

   

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

   

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

    

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

    

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

    

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

    

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

    

代码

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
    }
}