最大子数组分治算法加Strategy策略

1、前言

本文是在阅读算法导论的时候做的一点记录。加上前段时间阅读了《计算机科学丛书：设计模式可复用面向对象软件的基础》，在实现算法的时候顺便将Strategy设计模式运用其中，下面是详细讲解。

2、Strategy设计模式

策略（Strategy）设计模式是一种为了解决同一个目标可以通过多种途径（算法）达到的时候。例如一个人从A地到B地，可以使用自行车，汽车，飞机，轮船等途径（算法），而Strategy是将这些算法封装，可以使得使用者和算法本身分离的做法。（其实设计模式就是编程思路，理解后就觉得不神奇，但是在实际运用中真的有用）

3、最大子数组和问题

最大子数组问题是由计算股票最大收益引申而出，为了计算最大收益，将股价数组变为了今天的价格与昨天的价格差的数组，而最大收益就是这个数组的最大子数组和。

本文目前使用的《算法导论》中最基础的分治算法来解决，算法时间复杂度为O（n*log n），当然还有线性时间复杂度的算法，在此没做讨论。

4、正文

根据策略（Strategy）设计模式做出的大体结构如下：

最大子数组问题类：

/// 主要的类
class 最大子数组问题 {
    var strategy: 最大子数组协议
    init(withStrategy strategy: 最大子数组协议) {
        self.strategy = strategy
    }
}

最大子数组策略需要遵循的协议：

/// 采用策略（strategy）设计模式
/// 面向协议编程
protocol 最大子数组协议 {
    func find_maximum_subarray(A: Array<Int>)
        ->
        (maxLeft: Int, maxRight: Int, sum: Int)
}

采用分治思想的最大子数组和算法

/// 分治算法
class 最大子数组分治算法: 最大子数组协议 {
    /// 找到跨中位的最大子数组
    ///
    /// - Parameters:
    ///   - A: 原来的数组
    ///   - low: 最低位
    ///   - mid: 中位
    ///   - high: 最高位
    /// - Returns: 返回（左边边界，右边边界，最大子数组和）
    
    /// 时间复杂度为n，时间复杂度为常量
    func find_max_crossing_subarray
        (A: Array<Int>, low: Int, mid: Int, high: Int)
        ->
        (leftIndex: Int, rightIndex: Int, sum: Int)
    {
        var left_sum = Int.min // 当前最大的子数组和
        var sum = 0 // 左边数组总和
        var max_left = 0 // 记录最大的左边边界
        for i in (low...mid).reversed() { // 遍历mid～low（包括mid和low）
            // 时间复杂度为n
            sum += A[i]
            if sum > left_sum {
                left_sum = sum
                max_left = i
            }
        }
        
        var right_sum = Int.min // 当前最大的右边子数组和
        var max_right = 0 // 记录最大的右边边界
        sum = 0
        for i in mid+1 ... high { // 遍历mid+1～high-1
            // 时间复杂度为n
            sum += A[i]
            if sum > right_sum {
                right_sum = sum
                max_right = i
            }
        }
        
        return (max_left, max_right, left_sum + right_sum)
    }
    
    
    
    /// 寻找最大子数组
    ///
    /// - Parameters:
    ///   - A: 原来的数组
    ///   - low: 低位，可以递归调用
    ///   - high: 高位，可以递归调用
    /// - Returns: 返回元祖（低位的下标，高位的下标，最大子数组和）
    func find_maximum_subarray(A: Array<Int>, low: Int, high: Int)
        ->
        (maxLeft: Int, maxRight: Int, sum: Int)
    {
        if high == low { // 高位等于低位，查找范围只有一个数字，直接返回
            return (low, high, A[low])
        }
        else {
            let mid = (high-low)/2 + low // 这样的做法可以防止溢出
            // 假设最大子数组在中位数左侧, 递归调用自己
            let (left_low, left_high, left_sum) = find_maximum_subarray(A: A, low: low, high: mid)
            // 假设最大子数组在中位数的右侧, 递归调用自己
            let (right_low, right_high, right_sum) = find_maximum_subarray(A: A, low: mid+1, high: high)
            // 假设最大子数组跨越了中位数
            let (cross_low, cross_higth, cross_sum) = find_max_crossing_subarray(A: A, low: low, mid: mid, high: high)
            
            // 三种假设中，谁的子数组和计算出最大，就采用哪种方法
            if left_sum >= right_sum && left_sum >= cross_sum {
                return (left_low, left_high, left_sum)
            } else if right_sum >= left_sum && right_sum >= cross_sum {
                return (right_low, right_high, right_sum)
            } else {
                return (cross_low, cross_higth, cross_sum)
            }
        }
        
    }

/// 协议函数
    func find_maximum_subarray(A: Array<Int>) -> (maxLeft: Int, maxRight: Int, sum: Int) {
        if A.count == 0 {
            return (0, 0, 0)
        }
        return find_maximum_subarray(A: A, low: 0, high: A.count-1)
    }
}

Main函数中的使用

import Foundation
let strategy = 最大子数组分治算法()
var a = 最大子数组问题(withStrategy: strategy)
let arr = [1,-2,5,5,-12,3,6,10,-9,-3]

let date = Date()
let (left, right, sum) = a.strategy.find_maximum_subarray(A: arr, low: 0, high: 9)
print("time is : \(Date().timeIntervalSince(date)*1000.0)")

print("左边边界：\(left), 右边边界：\(right),和：\(sum)")

5、结语

分治算法本身没有过多讨论，这里是想实际运用Strategy策略设计模式，最大子数组分治算法是算法的使用者，但是它内部不包含任何算法的代码，而是指向一个Strategy（这个做法其实没看过设计模式也能想到，所以设计模式就是代码编写过程中的经验总结），而这个Strategy是由协议来规定格式（不同的语言可采用不同的方式，Swift中更偏向于协议编程，C++可能更喜欢用虚类）。

6、添加

增加暴力算法和扫描算法，
暴力算法时间复杂度为O（n2）
扫描算法时间复杂度为O（n）

暴力算法 O（n2）

class 最大子数组暴力算法: 最大子数组协议 {
    func find_maximum_subarray(A: Array<Int>) -> (maxLeft: Int, maxRight: Int, sum: Int) {
        if A.count == 0 {
            return (0, 0, 0)
        }
        var leftIndex = 0
        var rightIndex = 0
        var maxSum = Int.min
        
        for i in 0..<A.count {
            var temSum = 0
            for j in i..<A.count {
                temSum += A[j] // 先加上，如果加上一个比之前的大，则修改数据
                if temSum > maxSum {
                    maxSum = temSum
                    leftIndex = i
                    rightIndex = j
                }
            }
        }
        return (leftIndex, rightIndex, maxSum)
    }
}

扫描算法 O（n）

class 最大子数组扫描算法: 最大子数组协议 {
    
    /// 扫描一次的算法
    ///
    /// - Parameter A: 数组
    /// - Returns: 返回（左边界，右边界，和）
    func find_maximum_subarray(A: Array<Int>) -> (maxLeft: Int, maxRight: Int, sum: Int) {
        var leftIndex = 0
        var rightIndex = 0
        var sum = 0
        
        for i in 0..<A.count {
            if A[i] > 0 {
                sum += A[i]
                rightIndex = i
            } else if A[i] < 0 {
                if sum < 0 || (sum + A[i]) < 0 {
                    sum = 0
                    leftIndex = i
                    rightIndex = i
                }
            }
        }
        
        if leftIndex == rightIndex && leftIndex == A.count-1 && sum != A[rightIndex]{
            sum = A.max()! // 时间复杂度为n
            leftIndex = A.index(of: sum)! // 时间复杂度为n
            rightIndex = leftIndex
        }
        return (leftIndex, rightIndex, sum)
    }
}