题目：求最大子数组

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

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

分析：

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

思路：

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

代码：

  1. class FindMaxNum:
  2. 	def _find_crossing(self, A, low, mid, high):  # 寻找穿过中间值的最大子数组
  3. 		leftSum = float('-inf')
  4. 		ans = 0
  5. 		maxLeft = mid
  6. 		maxRight = mid + 1
  7. 		for i in range(mid, low - 1, -1):  # 找到左边的最大子数组
  8. 			ans += A[i]
  9. 			if ans > leftSum:
  10. 				leftSum = ans
  11. 				maxLeft = i
  12. 		rightSum = float('-inf')
  13. 		ans = 0
  14. 		for j in range(mid + 1, high + 1):  # 找到右边的最大子数组
  15. 			ans += A[j]
  16. 			if ans > rightSum:
  17. 				rightSum = ans
  18. 				maxRight = j
  19. 		return maxLeft, maxRight, leftSum + rightSum  # 返回最大的子数组以及它的两端下标
  22. 	def find_max_num(self, A, low, high):
  23. 		if low == high:  # 如果分到了1，那么就返回
  24. 			return low, high, A[low]
  25. 		else:
  26. 			mid = (low + high) // 2  # 将数组一分为二
  27. 			left_low, left_high, left_sum = self.find_max_num(A, low, mid)  # 递归进左子数组
  28. 			right_low, right_high, right_sum = self.find_max_num(A, mid + 1, high)  # 递归进右子数组
  29. 			cro_low, cro_high, cro_sum = self._find_crossing(A, low, mid, high)  # 寻找中间子数组
  30. 			if left_sum >= right_sum and left_sum >= cro_sum:  # 左边最大返回左边
  31. 				return left_low, left_high, left_sum
  32. 			elif right_sum >= left_sum and right_sum >= cro_sum:  # 右边最大返回右边
  33. 				return right_low, right_high, right_sum
  34. 			else:  # 否则中间最大返回中间
  35. 				return cro_low, cro_high, cro_sum
  37. if __name__ == '__main__':  # 测试通过
  38. 	test = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
  39. 	fn = FindMaxNum()
  40. 	i, j, res = fn.find_max_num(test, 0, len(test) - 1)
  41. 	print(test[i:j+1])
  42. 	print(i,j)
  43. 	print(res)

复杂度分析：

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

总结：

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