题目：求最大子数组

• 在一个数组中找到和最大的子数组。
• 数组中有正有负，但都是integer类型。

题目来源：算法导论第38页 4.1 最大子数组问题

分析：

根据书中的问题，采用分治思想来解题。具体可参考算法导论。

思路：

• 将整个数组一分为二，每次分完之后做四件事件：
  • 查看是否是最小数组即长度是1，因为数组长度是1那么总和就是这一个数的值。
  • 如果不是1，那就分别递归进左边的数组和右边的数组继续分，直到分到1再返回。
  • 每次递归除了左边的最大子数组和右边的最大子数组外，还有交叉在中间的最大子数组。所以要把中间的最大子数组也算出来。
  • 算出三者的各自的和将和最大的那个子数组并返回，同时返回它的两端下标。
• 每次递归都会返回左边，右边，中间的最大的那个子数组。
• 最后一次递归返回最大的子数组，答案就出来了。

代码：

class FindMaxNum:
	def _find_crossing(self, A, low, mid, high):  # 寻找穿过中间值的最大子数组
		leftSum = float('-inf')
		ans = 0
		maxLeft = mid
		maxRight = mid + 1
		for i in range(mid, low - 1, -1):  # 找到左边的最大子数组
			ans += A[i]
			if ans > leftSum:
				leftSum = ans
				maxLeft = i
		rightSum = float('-inf')
		ans = 0
		for j in range(mid + 1, high + 1):  # 找到右边的最大子数组
			ans += A[j]
			if ans > rightSum:
				rightSum = ans
				maxRight = j
		return maxLeft, maxRight, leftSum + rightSum  # 返回最大的子数组以及它的两端下标


	def find_max_num(self, A, low, high):
		if low == high:  # 如果分到了1，那么就返回
			return low, high, A[low]
		else:
			mid = (low + high) // 2  # 将数组一分为二
			left_low, left_high, left_sum = self.find_max_num(A, low, mid)  # 递归进左子数组
			right_low, right_high, right_sum = self.find_max_num(A, mid + 1, high)  # 递归进右子数组
			cro_low, cro_high, cro_sum = self._find_crossing(A, low, mid, high)  # 寻找中间子数组
			if left_sum >= right_sum and left_sum >= cro_sum:  # 左边最大返回左边
				return left_low, left_high, left_sum
			elif right_sum >= left_sum and right_sum >= cro_sum:  # 右边最大返回右边
				return right_low, right_high, right_sum
			else:  # 否则中间最大返回中间
				return cro_low, cro_high, cro_sum

if __name__ == '__main__':  # 测试通过
	test = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
	fn = FindMaxNum()
	i, j, res = fn.find_max_num(test, 0, len(test) - 1)
	print(test[i:j+1])
	print(i,j)
	print(res)

复杂度分析：

• 时间复杂度：O(nlogn) n 为数组的长度
• 空间复杂度：O(1) 完全没有开辟新的数组空间，仅仅是在原数组上分治。

总结：

• 分治算法可以大幅度提高运行效率，相比于暴力法，速度提升很多。
• 算法导论上的这个分治法应该是我看到的最好的分治法了，很多地方的算法解这道题时总是会开辟新的数组，这就导致了内存空间的浪费，如果数据量多的话，很容易空间不够。
• 分治的主要思想就是找到递归条件和线性条件。然后用分而治之的方法从线性条件不停地向前合并，最终找到答案。主要的原理和递归很像。