求解最大子数组

暴力破解法

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

算法复杂度 $$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 也是可以省略的