1、什么是最大连续子序列和问题？

问题描述：给定一个序列（整数或浮点数），求出其中连续的子序列和最大的那一个。

问题举例：序列{-10 1 2 3 4 -5 -23 3 7 -21}，其最大的连续子序列为{1 2 3 4}或{3 7}，最大和为10.

2、方法一：暴力求解

最普通的方法，效率十分低，一般不会用到，这里简单介绍。直接两个for循环枚举子序列的首尾，再来一个for循环计算首尾之间的序列和，计算所有的序列和，找到最大值。

时间复杂度：O(n^3)，代码低效 不贴代码

3、方法二：预处理暴力求解

第一种方法为什么这么慢，原因之一是每次都要计算首尾之间的序列和。基于这个考虑，我们可以对数据进行预先处理：读入数据时使用一个数组SUM[i]来记录前i项数据之和。用这种方法，只需要两个for循环枚举子序列的首尾，利用SUM数组计算子序列和，找到最大值。

时间复杂度：O(n^2) 代码低效 不贴代码

4、方法三：分治法求解

把序列分成左右两部分，一般对半分，数量不等也没关系。最大子序列和的位置存在三种情况：1、完全在左半部分；2、完全在右半部分；3、跨越左右两部分。分别求出左半部分的最大子序列和、右半部分的最大子序列和、以及跨越左右两部分的最大子序列和，三者中的最大者就是要求的。

如何求三部分的最大子序列和呢？

左半部分的最大子序列和，可把左半部分作为新的输入序列通过该算法递归求出。右半部分的最大子序列和同理。

接下来就是求解跨越左右两部分的最大子序列和，也就是求出包含左半部分中最右边元素的子序列的最大和，和包含右半部分中最左边元素的子序列的最大和，将两者相加即为跨越左右两个部分的最大子序列和。

具体见如下代码：

分治法求解

时间复杂度：O（nlgn）

运用递归思想，一层一层分解，最终解决问题。效率还好，有助于理解分治与递归，可以尝试使用。

5、方法四：动态规划

这是最常见的方法了，简单有效，好理解。

状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大序子列连续和)

其实完全可以不用开数组，累计sum直到sum + a < a，把sum赋值为a，更新最大值就行了。

//动态规划算法int MaxSum(int n){    int sum=0,b=0;    for(int i=0;i<n;i++)    {        if(b>0) b+=a[i];        else b=a[i];        if(b>sum) sum=b;    }    return sum;}

时间复杂度：O（n）

这是好用的求最大子序列的方法了，墙裂推荐！