Question

最大子数组问题的几种解法

Answer 1

最近看到《算法导论》的分治策略一节，看到的一个题目可以优化引申出来多种解法，同时也可以帮助理解分治策略的化整为零和动态规划的动态转移方程的思维。

最大子数组：数组 A 中的和最大的非空连续子数组。

这个问题可以用暴力解法，两层循环遍历，时间复杂度为 O(n^2)，当然最容易想到的并不是最好的解法。

可以得知最大的和为 43，即下标 7, 10 之间的子数组。

既然这一节是讲分治策略，那么怎么用分治的思想来优化呢。这个解法确实比较难懂，如果让脑袋去跑一遍递归，真的有点累。那么分治本来就是一种局部整体的思想，我们把切片分成三组，左，中，右。那么我们只需要得出，这三个子集的最大值即可。然后再不断分化下去，最后把最大值冒上来。分治解法的关键就是如何用整体局部的思想把问题抽象化。

可以将时间复杂度降低到 O(n) 吗？ 动态规划。

从题目上看，可以发现这道题满足动态规划的思想。可以求得动态转移方程为：F(n) = max(F(n-1)+A[n], A[n])

53 最大子序和