初级算法-动态规划-最大字序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

摘一个示例做个说明.
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

条件分析:

1. 最大和的连续子数组

解决思路1:

1. 根据分析1,说明数据有正数有负数.当前最大和就是前面到当前位置中和最大的数,先找第一个,然后和后面相加的进行比较.

采用循环判断存储,然后当前和与之前和进行找最大值.最大的那个就是最后返回的最大和.

func maxSubArray(_ nums: [Int]) -> Int {
    var dp = [Int](repeating: 0, count: nums.count)
    dp[0] = nums[0]
    var maxSum = dp[0]
    for i in 1..<nums.count {
        dp[i] = max(dp[i-1]+nums[i],nums[i])
        maxSum = max(dp[i], maxSum)
    }
    return maxSum
}

![最大字序和提交结果.jpg](https://img.haomeiwen.com/i2856483/96ed887666db3368.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

测试用例:

let num = [1]
let num = [-1]
let num = [0]
let num = [1,2,3,-3,4,7,-2,9,8,-10,2,13,0]

考察要点:

• 数组
• 分治
• 动态规划