对最大子段和的理解（动态规划）

问题

对一个长度为n的数组，找到连续的子段，使它的和在所有子段中是最大的。

比如3，4，-9，6。他们的最大子段和是7。

解法

A.遍历

O(n)=n^2

B.分治算法

O(N)=N*logN

数组分为Left与Right部分，最大字段和要么在left，要么在right，要么必然包括mid-1与mid+1（这种情况复杂度仅为n，此处mid不代指元素，mid-1与mid+1相邻），籍此可以递归求解。

比如 2，3，-5，6，9可以分为2，3与-5，6，9。左最大子段和5，右最大子段和15，经过3与-5的最大子段和15。三者选最大的15作为结果。

C.动态规划

将输入数组描述为a1到an的整数序列，令bj为a1到aj序列中包含aj的最大子段和。由此可以推导，最大字段和是b1到bn的集合中的最大值。

其实动态规划解法是分治解法的特殊情况，即right的长度为1.此时最大子段和，要么在左边，要么从mid+1开始向左找。

但他们的复杂度并不相同，动态规划解法复杂度为n。

在解法B中，每次的left和right不同，其实丢失了一部分信息。而在解法C中，每次left长度都+1，并且上一次的b被保留。

此时最大子段和仍然要么在左边，要么从mid+1向左找，但向左找的过程可以简化成常数时间（不直接找最大子段和，而是找b，仅仅找经过aj的最大子段和），也就是说不用考虑mid+1以外的项开头的段。

因为bj的计算一定会经过mid-1或者就是aj本身，所以比较b(j-1)+aj与aj就能确定新的bj（不是新的最大字段和）。为什么有b(j-1)+aj的式子呢，可以用归纳法推导：j=2时，经过a2的最大和要么是a2，要么是a1+a2；j=3时，经过a3的最大和要么是a3，要么是b2+a3。可以看出来，无论是a2还是a1+a2，都可以和a3连起来，选择max(a2,a1+a2)+a3或a3就选择了最大子段和。