给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
摘一个示例做个说明.
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
条件分析:
- 最大和的连续子数组
解决思路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
}
测试用例:
let num = [1]
let num = [-1]
let num = [0]
let num = [1,2,3,-3,4,7,-2,9,8,-10,2,13,0]
考察要点:
- 数组
- 分治
- 动态规划
