经典算法（一）-最大子列和问题

最近在慕课上听浙江大学陈越老师的《数据结构》，在看之前对比了一些其他的学校的《数据结构》这门课，最后选择了陈姥姥的课。陈姥姥的课讲的真心好，就是课后题的难度有点大。是真心有点难。。。

第一周课后作业的基础题是最大子列和。做了一下，下面和大家分享一下：

题目：给定K个整数组成的序列{N1,N2, ...,NK}，“连续子列”被定义为{Ni,Ni+1, ...,Nj}，其中1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

那么首先第一种方法：简单粗暴直接求出所有子列的和，然后在比较。

算法复杂度：程序中使用了三层for循环，所有复杂度应为三个for循环循环次数的乘积。即n的三次方。

这是个足够笨的办法，但也能基本解决问题，不过当n超过10000时，程序执行所需要的时间就有点可怕了。

我们就先定个小目标，简单优化一下，把算法复杂度降为N平方吧。

设计思路：列出所有子列和比较出最大子列和，较上一方案的优化是在计算子列和时对于相同的j不同的k计算子列时候只是k-1的循环基础上的结果加上Num[k]。

算法复杂度：两层for循环嵌套复杂度为N的两次方

下面是我的程序：

这个算法确实是优化了一下，但它依然是个不及格的方案。

方法三，分而治之。分而治之算是个很经典的程序设计方法了，简单来说就是把一个大问题分成两个小问题，如果小问题还是复杂那么就再次划分，以此类推，最后只要把每个小问题都解决，那么大问题也就迎刃而解了。

那么针对这道题怎么使用分而治之法呢？

将整个数组从中间分为两部分，将问题变为三个小问题：

1）求左边子列和的最大值2）求右边子列和的最大值3）左右两边子列和最大值的和

算法复杂度：NlogN

程序如下：

这个方法实现起来的算法复杂度为NlogN，对这道题而言，算是勉强及格吧。

好了，那就看看我最终的实现方法吧在线处理。

程序如下：

这个算法的复杂度是N，这应该是解决这个问题最快的方法了吧。最后我把这个程序输进去，也终于得了满分，20分。别高兴，这只是陈姥姥留的三道课后题中最简单的一道。剩下两道题，留着下期更新。。。。