一道算法题，看看大家的思路（续）-阿里云开发者社区

一道算法题，看看大家的思路（续）

2017-11-15 1009

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

　“一道算法题，看看大家的思路”，看了众多的回复，本人愚钝，没有看明白其中的奥妙。在细细研究《编程之美》中的文章后，终于理解了这个算法的思路。现将这个算法的演算过程以及代码实现（VB2005）赋予其后，和各位交流。

　　现再将题目复述一遍：

　　题目描述：有31，-41，59，26，-53，58，97，-93，-23，84十个数。SUM（N，M）表示从第N个数到到第M个数的和。例如：SUM（2，3）=-41+59=18。问：最大的和是多少？对应的N和M是多少？

　　先不管N和M的计算，直接计算SUM，看看用什么算法。

　　算法一：直接遍历穷举，求出SUM。代码如下：

　　 Public Function MaxSum1() As Integer
　　　　 Dim i As Integer, j As Integer, k As Integer, _
Sum As Integer, Maximum As Integer = Integer.MinValue

For i = 0 To A.GetUpperBound(0)
For j = i To A.GetUpperBound(0)
Sum = 0
For k = i To j
Sum += A(k)
If Sum > Maximum Then Maximum = Sum
Next
　　　　　　 Next
　　　　 Next
　　　　 Return Maximum
End Function

　　这个代码最容易理解，但是效率最低，算法的复杂度为O(N³)

　　算法二，在算法一的基础上改进，因为SUM（N，M）=SUM（N，M-1）+A（M），基于这个原理，将上述代码中的最里面的一层循环去掉。

　　 Public Function MaxSum2() As Integer
　　　　 Dim i As Integer, j As Integer, Sum As Integer, _
Maximum As Integer = Integer.MinValue
For i = 0 To A.GetUpperBound(0)
Sum = 0
For j = i To A.GetUpperBound(0)
Sum += A(j)
If Sum > Maximum Then Maximum = Sum
Next
　　　　 Next
　　　　 Return Maximum
End Function

　　这个代码也很容易理解，算法执行效率有明显的提高，算法的复杂度为O(N²)，但还不够。

　　算法三：

　　考虑数组第一个元素A（0）和最大和的一段数组A（N），……，A（M）。他们之间有如下关系：

　　1、当0=N=M时，元素A（0）本身构成最大和的一段

　　2、当0=N<M时，最大和的一段以A（0）开始

　　3、当0<N时，A（0）和最大和一段没有什么关系。

　　假设数组有N个元素，分别为A（0），A（1），……，A（N-1）

　　并且我还知道从A（1）到A（N-1）的最大和为All（1），从A（1）到A（N-1）中包含A（1）的最大和为Start（1）

　　那么，从A（0）到A（N-1）的最大和All（0）就一定有下面的关系式：

　　All（0）=Max｛A（0），A（0）+Start（1），All（1）｝

　　而Start（0）有如下的关系式：

　　Start（0）=Max｛A（0），A（0）+Start（1）｝

　　看了上面的分析，将N个元素的问题就转化为了N-1个元素的问题。这是我想到了递推。（书上以及很多其他的博客说是动态规划，我没有理解，个人比较愚钝）

　　将上面的式子整理一下，建立好递推关系：

　　Start（i）=Max｛A（i），A（i）+Start（i+1）｝

　　All（i）=Max｛Start（i），All（i+1）｝

　　代码如下：

　　 Public Function Max( ByVal X As Integer, ByVal Y As Integer) As Integer
　　　　 Return IIf(X > Y, X, Y)
End Function

　　 Public Function MaxSum3() As Integer
　　　　 Dim i As Integer, Start() As Integer, All() As Integer
　　　　 ReDim Start(A.GetUpperBound(0))
ReDim All(A.GetUpperBound(0))

Start(A.GetUpperBound(0)) = A(A.GetUpperBound(0))
All(A.GetUpperBound(0)) = A(A.GetUpperBound(0))

For i = A.GetUpperBound(0) - 1 To 0 Step -1
Start(i) = Max(A(i), A(i) + Start(i + 1))
All(i) = Max(Start(i), All(i + 1))
Next

　　　　 Return All(0)
End Function

　　这个算法的效率很高，算法复杂度为O(N)，但是引用了两个数组。仔细观察两个数组的使用情况，发现其实只要使用两个变量就完全可以了，下面是改进的代码。

　　 Public Function Max( ByVal X As Integer, ByVal Y As Integer) As Integer
　　　　 Return IIf(X > Y, X, Y)
End Function

　　 Public Function MaxSum4() As Integer
　　　　 Dim i As Integer, Start As Integer, All As Integer
　　　　Start = A(A.GetUpperBound(0))
All = A(A.GetUpperBound(0))
For i = A.GetUpperBound(0) - 1 To 0 Step -1
Start = Max(A(i), A(i) + Start)
All = Max(Start, All)
Next
　　　　 Return All
End Function

　　将上面的代码，仔细分析一下可以发现：

　　Start=Max（A（i），A（i）+Start）

　　可以改写为：

　　If Start<0 Then

　　　　Start=A（i）

　　Else

　　　　Start=A（i）+Start

　　End If

　　继而可以改写为

　　If Start<0 Then Start=0

　　Start=A（i）+Start

　　而All = Max(Start, All)可以改写为

　　If Start>All Then All=Start

　　故上面的代码，可以改写为一个函数，减少系统的开销

　　 Public Function MaxSum5() As Integer
　　　　 Dim i As Integer, Start As Integer, All As Integer
　　　　Start = A(A.GetUpperBound(0))
All = A(A.GetUpperBound(0))

For i = A.GetUpperBound(0) - 1 To 0 Step -1
If Start < 0 Then Start = 0
Start += A(i)

If Start > All Then All = Start
Next
　　　　 Return All
End Function

至此，代码效率高，又简洁明了。唯一的缺憾是从数组的最后一个倒推，下面的代码改成正推

　　 Public Function MaxSum6() As Integer
　　　　 Dim i As Integer, Start As Integer, All As Integer
　　　　Start = A(0)
All = A(0)

For i = 1 To A.GetUpperBound(0)
If Start < 0 Then Start = 0
Start += A(i)

If Start > All Then All = Start
Next

　　　　 Return All
End Function

　　以上的推导过程就是为了求出一个最大和，没有求出具体的下标。关于下标的计算，留待后文详述。

　　代码格式修正于2012年1月6日

本文转自万仓一黍博客园博客，原文链接：http://www.cnblogs.com/grenet/archive/2010/02/21/1670208.html，如需转载请自行联系原作者