LeetCode最大子序和Swift

给定一个整数数组 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
    }
}