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
    }