数据结构与算法分析笔记——最大子序列和：给定整数A1，A2，……，AN，求∑k=ijAk
给定整数A1，A2，……，AN，求∑k=ijAk
说明：
整数可能为负。为方便计算，若序列所有整数均为负，则最大子序列和为0。例：对于输入-2，11，-4，13，-5，-2，答案为20（从A2到A4)。算法1
算法1说明：
这个算法的思路是最显然的，也是最直接的。就是穷举所有可能的子序列的和，然后比较得到最大值。从输入序列的任意元素开始，跨域任意长度，到达任意元素止，都可以构成一个子序列。所以我们看到，算法中包含了三个for循环，由外而内，第一层循环从0开始，取起点，第二层循环，从起点开始，跨越长度，取终点，第三层循环用于计算子截取到的子序列的和。
算法分析：
三层循环，每层最坏都可能要计算N次，所以，它的运行时间为O(N3)。
算法2
算法2说明：
这个算法显然是在第一个算法的基础上优化的。基于一个最基本的公式，∑k=ijAk=Aj+∑k=ij1Ak。没明白？通俗的举个例子，假设有两个子序列，第一个子序列是从第2到第8个元素，第二个子序列是从第2到第9个元素，那么，很显然，第二个子序列的和为第一个子序列的和加上第9个元素。也就是说，算法1中，第三个循环通过元素逐个累加计算子序列的值是没必要的，可以通过上一个子序列的结果直接得出。
算法分析：
很显然，少了一层循环，它的运行时间为O(N2)。
算法3
算法3说明：
要看懂这个算法，就需要花点力气了。
首先，我们聊一个在解决问题时常用的一种策略，叫做“分治”策略。就是先把一个问题分解成两个大致相等的子问题，分别得到两个子问题的解，这是分。接下来，再把两个子问题的解修补到一起，可能还需要一些额外的工作，最终得到整个问题的答案，这就是治。
回到最大子序列和的问题，看看如何应用分治策略。
假设，将一个序列分成大致相等的两段，那么，最大子序列可能出现的位置有三种情况：第一段，第二段，或者是跨域分割点，横占两段。横占两段的和最大的子序列，一定是第一段中包含右端点的最大子序列和第二段中包含左端点的最大子序列的和。
有了这个思路后，再看算法3，一个典型的递归算法。先是不断的分，得到分中的最大子序列和，再治，取得分中的最大子序列和以及横跨两部分中最大子序列和中的最大值，即为最终得到的解。
算法分析：
算法3从思路还是代码长度来说，都要比算法1或2复杂，那么，它的运行时间又如何呢？
算法中，首先，取横占两段的最大和的部分，一个循环是中点到起点，另一个是从中点到终点，加起来刚好是O(N)。再看递归，递归的复杂度要看它每次递归能减小多少计算规模。我们是从中点分开的，也就是说，假设不考虑横占两段的循环部分，每次递归，都会把计算规模缩小一半。又有当N=1时，在第一个判断就能得到结果，记为1，则我们得到如下方程组：
T(1)=1
T(N)=2T(N/2)+O(N)
O(N)可以用N来代替，得到如下
T(1)=1
T(N)=2T(N/2)+N
于是，我们有T(1)=1,T(2)=2*1+2=4，T(4)=2*4+4=12，T(8)=2*12+8=32。
归纳整理，可以得到T(N)=O(NlogN)。显然，算法3是优于算法2和算法1的。
算法4
算法4说明：
如果没有算法4，那么，算法3是一个不错的选择。我们知道，有以下几个常见的算法运行时间，按数量级递增，有O(1)，O(logN)，O(N)，O(NlogN)，O(N2)，O(N3)等。
算法3的复杂度是O(NlogN)，那么，算法4到底是如何成立的？它是否真的能得到最大子序列和？
考虑以下规则：
设有a、b、c三个序列中的任意元素，有A、B两个任意子序列的和，有如下：
如果ab，则a+cb+c；如果AB，则A+cB+c;尝试用这两个规则，去理解算法4。算法分析：
算法4的复杂度是O(N)，显然，比前几个算法都要优。