【出自HW面试题】
难度系数：★★★★☆ 被考察系数：★★★★★
题目描述：
一个有n个元素的数组，这n个元素既可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值。例如：对于数组{1，-2，4，8，-4，7，-1，-5}而言，其最大和的子数组为{4，8，-4，7}，最大值为15。
分析与解答：
这是一道在笔试面试中碰到的非常经典的算法题，有多种解决方法，下面分别从简单到复杂逐个介绍各种方法。
方法一：蛮力法
最简单也是最容易想到的方法就是找出所有的子数组，然后求出子数组的和，在所有子数组的和中取最大值。实现代码如下：
程序的运行结果如下：
连续最大和为：15
算法性能分析：
这种方法的时间复杂度为O（n^3），显然效率太低，通过对该方法进行分析发现，许多子数组都重复计算了，鉴于此，下面给出一种优化的方法。
方法二：重复利用已经计算的子数组和
由于Sum[i，j]=Sum[i，j-1]+arr[j]，在计算Sum[i，j]的时候可以使用前面已计算出的Sum[i，j-1]而不需要重新计算，采用这种方法可以省去计算Sum[i，j-1]的时间，因此，可以提高程序的效率。
实现代码如下：
算法性能分析：
这种方法使用了双重循环，因此，时间复杂度为O（n^2）。
方法三：动态规划方法
可以采用动态规划的方法来降低算法的时间复杂度。实现思路如下。(www.xing528.com)
首先可以根据数组的最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论：
（1）最大子数组包含arr[n-1]，即最大子数组以arr[n-1]结尾。
（2）arr[n-1]单独构成最大子数组。
（3）最大子数组不包含arr[n-1]，那么求arr[1…n-1]的最大子数组可以转换为求arr[1…n-2]的最大子数组。
通过上述分析可以得出如下结论：假设已经计算出子数组arr[1…i-2]的最大的子数组和All[i-2]，同时也计算出arr[0…i-1]中包含arr[i-1]的最大的子数组和为End[i-1]。则可以得出如下关系：All[i-1]=max{End[i-1]，arr[i-1]，All[i-2]}。利用这个公式和动态规划的思想可以得到如下代码：
算法性能分析：
与前面几个方法相比，这种方法的时间复杂度为O（N），显然效率更高，但是由于在计算的过程中额外申请了两个数组，因此，该方法的空间复杂度也为O（N）。
方法四：优化的动态规划方法
方法三中每次其实只用到了End[i-1]与All[i-1]，而不是整个数组中的值，因此，可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用。实现代码如下：
算法性能分析：
这种方法在保证了时间复杂度为O（N）的基础上，把算法的空间复杂度也降到了O（1）。
引申：在知道子数组最大值后，如何才能确定最大子数组的位置？
分析与解答：
为了得到最大子数组的位置，首先介绍另外一种计算最大子数组和的方法。在上例的方法三中，通过对公式End[i]=max（End[i-1]+arr[i]，arr[i]）的分析可以看出，当End[i-1]＜0时，End[i]=array[i]，其中End[i]表示包含array[i]的子数组和，如果某一个值使得End[i-1]＜0，那么就从arr[i]重新开始。可以利用这个性质非常容易地确定最大子数组的位置。
实现代码如下：
程序的运行结果如下：
连续最大和为：15
最大和对应的数组起始与结束坐标分别为：2，5
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
