给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路：
“动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。”
解法一
class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count>0 else { return 0 } //创建一个和nums同长度的数组，初始化全为0，用来存储之前元素的最大和 var dp = [Int](repeating: 0, count: nums.count) dp[0] = nums[0] //此变量用来记录最大和 var maxSum = dp[0] for i in 1 ..< nums.count { //dp[i-1] 是正数就加当前元素值 是负数就从当前元素开始计算最大值 if dp[i-1] > 0 { dp[i] = dp[i-1] + nums[i] } else { dp[i] = nums[i] } } //for循环dp数组查找最大和 for i in 1 ..< nums.count { if dp[i] > maxSum { maxSum = dp[i] } } return maxSum } }
代码优化：只for循环一遍nums，同时求出最大和
class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count>0 else { return 0 } //创建一个和nums同长度的数组，初始化全为0，用来存储之前元素的最大和 var dp = [Int](repeating: 0, count: nums.count) dp[0] = nums[0] //此变量用来记录最大和 var maxSum = dp[0] for i in 1 ..< nums.count { //dp[i-1] 是正数就加当前元素值 是负数就从当前元素开始计算最大值 if dp[i-1] > 0 { dp[i] = dp[i-1] + nums[i] } else { dp[i] = nums[i] } //for循环dp数组查找最大和 if dp[i] > maxSum { maxSum = dp[i] } } return maxSum } }
继续代码优化
class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count>0 else { return 0 } //创建一个和nums同长度的数组，初始化全为0，用来存储之前元素的最大和 var dp = [Int](repeating: 0, count: nums.count) dp[0] = nums[0] //此变量用来记录最大和 var maxSum = dp[0] for i in 1 ..< nums.count { //dp[i-1] 是正数就加当前元素值 是负数就从当前元素开始计算最大值 dp[i] = max(dp[i-1] + nums[i], nums[i]) //for循环dp数组查找最大和 maxSum = max(maxSum, dp[i]) } return maxSum } }
继续代码优化：不用动态规划，节省内存空间
class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count>0 else { return 0 } //此变量用来记录最大值 var ans = nums[0] //用来记录之前元素的最大和 是正数就加当前元素值 是负数就从当前元素开始计算最大值 var maxSum = 0 for num in nums { if maxSum > 0 { maxSum += num } else { maxSum = num } ans = max(ans, maxSum) } return ans } }
原文：https://www.cnblogs.com/huangzs/p/14069591.html