暴力破解法

通过遍历每个子数组，找到最小的子数组

>算法复杂度 $$n^2$$

func FindMaxSubArr(A []int) (int, int, int) {
    var max = A[0]
    var current = 0
    var left, right = 0, 0
    var LengthA = len(A)
    for i := 0; i < LengthA; i++ {
        current = A[i]
        if current > max { // 判断初始的单元是否是最大数组,第一次写的时候忘记加了，导致有些排列会出问题
            max = current
            left, right = i, i
        }
        for k := i + 1; k < LengthA; k++ {
            current += A[k]
            if current > max {
                max = current
                left, right = i, k
            }
        }
    }

    return left, right, max
}

分治法

分解数组规模，递归的求解左右子数组及跨越中间的数组。
将数组分为两部分，最大子数组要么在左边的子数组，要么在右边的子数组，要么跨越两个子数组

>算法复杂度 $$n log(n)$$

func FindMaxSubArr(A []int) (int, int, int) {
    if len(A) == 1 {
        return 0, 0, A[0]
    }
    middle := len(A) / 2
    ll, lr, lm := FindMaxSubArr(A[:middle])
    rl, rr, rm := FindMaxSubArr(A[middle:])
    ml, mr, mm := FindCrossMiddleSubArr(A[:])

    if lm >= rm && lm >= mm {
        return ll, lr, lm
    } else if rm >= lm && rm >= mm {
        return rl + middle, rr + middle, rm
    } else {
        return ml, mr, mm
    }
}

func FindCrossMiddleSubArr(A []int) (int, int, int) {
    lens := len(A)
    if lens == 1 {
        return 0, 0, A[0]
    }
    middle := lens / 2
    left, right := middle-1, middle
    lmax, rmax := A[left], A[right]
    ltemp := lmax
    rtemp := rmax
    i := left
    k := right
    for i > 0 {
        i--
        ltemp += A[i]
        if lmax < ltemp {
            lmax = ltemp
            left = i
        }
    }

    for k < lens-1 {
        k++
        rtemp += A[k]
        if rmax < rtemp {
            rmax = rtemp
            right = k
        }
    }

    return left, right, lmax + rmax
}

动态规划

若已知 A[1.. j] 的最 大子数组，基于如下性质将解扩展为 A[1. .j+1] 的最大子数组： A[1. .j+1] 的最大子数组要么是 A[1.. j] 的最大子数组，要么是某个子数组 A[i.. j+1])
简单的理解，给一个已知最大子数组的数组增加一个单元，新数组的最大子数组如果产生了变化，会有两种情况：

  1. 最大子数组不变
  2. 最大子数组内包含新增的单元

初版错误的代码

func FindMaxSubArr(A []int) (int, int, int) {
    max := A[0]
    left, right := 0, 0

    leftToNow := max
    tempLeft := left
    for i := 1; i < len(A); i++ {
        leftToNow = leftToNow + A[i]
        if leftToNow > max && leftToNow > A[i] {
            max = leftToNow
            left = tempLeft
            right = i
        } else if A[i] > leftToNow && A[i] > max {
            max = A[i]
            leftToNow = max
            left, right = i, i
            tempLeft = left
        }
    }

    return left, right, max
}

随机测试发现 类似序列 [-8 -4 6 -8 5 7 -5 6 -1 -7] 并不能正常生成最大子数组。
问题在于左界只会因为之前的子数组小于当前单元时会右移重置，会导致计算的最大子数组中包含了左侧连续的和为负的子数组，导致整体的和变小。
解决这个问题，我们需要知道。 x < 0, x + P <= P
我们需要动态的舍去已经计算出的负数子数组。当前子数组的和已经小于零，那么不论下一个单元是正是负，都会大于或者等于当前的子数组的合。

 else if leftToNow < 0 {
    leftToNow = 0
    tempLeft = i + 1
}

再次测试的时候，发现还是有问题，问题出在这两行

if leftToNow >= max && leftToNow > A[i]

} else if A[i] > leftToNow && A[i] > max {

我们仅当 leftNow > A[i] 时才更新 max, 但是通过上面的代码，我们可能已经将leftToNow 更新成了 A[i] , 因此它将永远不会成立。
我们只需要将两个条件中的任意一个 leftToNow 与 A[i] 的比较进行 == 的判断就可以了

>算法复杂度 $$n$$

func FindMaxSubArr(A []int) (int, int, int) {
    max := A[0]
    left, right := 0, 0

    leftToNow := max
    tempLeft := left
    for i := 1; i < len(A); i++ {
        leftToNow = leftToNow + A[i]
        if leftToNow > max && leftToNow >= A[i] {
            max = leftToNow
            left = tempLeft
            right = i
        } else if A[i] > leftToNow && A[i] > max {
            max = A[i]
            leftToNow = max
            left, right = i, i
            tempLeft = left
        } else if leftToNow < 0 {
            leftToNow = 0 // 循环开始时会被初始化为 A[i+1] 的值，不会产生负面影响
            tempLeft = i + 1
        }
    }

    return left, right, max
}

实际上 如果采用

} else if A[i] >= leftToNow && A[i] > max {

tempLeft = i + 1 也是可以省略的