swift算法：最大子序和

1、描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例1：输入：[-2, 3, -1, 1, -3]

          输出：3

          解释：连续子数组 [3, -1, 1] 的和最大，为3

例2：输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

          输出：6

          解释：连续子数组 [4, -1, 2, 1] 的和最大，为6

2、算法

解法一：暴力循环解法

思路：遍历一遍，用两个变量，一个记录最大的和，一个记录当前的和，最后找出连续子数组最大的和

时间复杂度：O(n^2)

func maxSubArray(_ nums: [Int]) -> Int {
        /*
        暴力循环遍历 O(n^2)
         */
        var nums = nums
        //存最大值
        var maxValue = nums[0]
        var sum = 0
        
        for i in 0..<nums.count {
            sum = 0
            for j in i..<nums.count{
                sum += nums[j]
                if sum > maxValue{
                    maxValue = sum
                }
            }
        }
        return maxValue
    }
           

解法二：动态规划

思路：

1）动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans

2）如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字

3）如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字

4） 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

图示：

时间复杂度：O(n)

func maxSubArray(_ nums: [Int]) -> Int {
       
        var nums = nums
        var ans = nums[0]
        var sum : Int = 0
        for num in nums {
            if sum > 0{
                sum += num
            }else{
                sum = num
            }
            ans = max(ans, sum)
            
        }
        return ans
    }
           

3、进阶

如果你已经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。

解法一：非递归分治

思路：

1）定义一个max记录过程中最大值

2）定义lSum、rSum从两头向中间推进的记录的两个最终子序和

3）到中间汇聚，再取最大值：Math.max(max, lSum+rSum);

func maxSubArray(_ nums: [Int]) -> Int {
        
        var nums = nums
        //过程中最大值
        var maxValue = max(nums[0], nums[nums.count-1])
        //左半部分，最近一次子序和
        var lSum = 0
        //右半部分，最近一次子序和
        var rSum = 0
        
        var i = 0, j = nums.count-1
        while i<=j {
            lSum = lSum>0 ? lSum+nums[i] : nums[i]
            maxValue = max(maxValue, lSum)
            
            if j != i {
                rSum = rSum>0 ? rSum+nums[j] : nums[j]
                maxValue = max(maxValue, rSum)
            }
            
            i += 1
            j -= 1
        }
        
        //汇聚
        //maxValue 左右两边最大的，lSum+rSum 中间聚合
        return max(maxValue, lSum+rSum)
    }
           

解法二：递归分治

思想：通过递归分治不断的缩小规模，问题结果就有三种，左边的解，右边的解，以及中间的解（有位置要求，从中介mid向两边延伸寻求最优解），得到三个解通过比较大小，等到最优解。

时间复杂度：O(nlogn)

func maxSubArray3(_ nums: [Int]) -> Int {
        return maxSubArrayPart(nums, 0, nums.count-1)
    }
    private func maxSubArrayPart(_ nums : [Int], _ left : Int, _ right : Int)->Int{
        if left == right {
            return nums[left]
        }
        
        let mid = (left+right)/2
        return max(maxSubArrayPart(nums, left, mid), max(maxSubArrayPart(nums, mid+1, right), maxSubArrayAll(nums, left, mid, right)))
    }
    //左右两边合起来求解
    private func maxSubArrayAll(_ nums : [Int], _ left : Int, _ mid : Int, _ right : Int)->Int{
        var leftSum = -2147483648
        var sum = 0
        var i = mid
        while i >= left {
            sum += nums[i]
            if sum > leftSum {
                leftSum = sum
            }
            i -= 1
        }
        sum = 0
        var rightSum = -2147483648
        var j = mid+1
        while j<=right {
            sum += nums[j]
            if sum > rightSum{
                rightSum = sum
            }
            j += 1
        }
        
        return leftSum+rightSum
    }