对最大子段和的理解(动态规划)

问题

对一个长度为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就选择了最大子段和。

留下评论