问题描述：给定n个整数序列{a1,a2,...,an},求函数f(i,j)=max{0,σak}(k:连续的从i取到j);
问题即为求已连续子列和的最大值，若果最大值为负数则取0，比如8个数序列{-1,2，-3,4，-2,5，-8,3}，那摩最大子序列和为4+（-2）+5=7.
这个问题有四种不同复杂度的算法，算法1到四的时间复杂度是o(n3),o(n2),o(nlogn),o(n);
算法一：
最直接的方法是穷举法，列出所有的情况，我们可以设定子序列的左端i和右端j,再利用一层计算出a[i]到a[j]的和.
//最大子列和穷举法
#include
using namespace std;
int find_maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int find_maxsun(int*a, int n){
int maxsun = 0, i, j, k;
int nowsum;
for (i = 0; i for (j = 0; j nowsum = 0;
for (k = i; k nowsum += a[k]; /*从a[i]到a[j]的子序列*/
if (nowsum>maxsun)
maxsun = nowsum; /*更新结果*/
}
return maxsun;
}
很显然，暴力法使用啦3重for循环，算法时间复杂度为o(n3)，这当然也是一个最笨的算法，但数据难非常庞大时候，哪怕是要算到死的节奏，我们可以清楚看到第三层for循环，
j每加一次，子列和都要重头算一次，那我们为何不去利用j-1的结果呢？也就是说我们将j-1的结果保存下来，在计算j步的结果时候，只需要在j-1步的基础上再加上a[j]，就可以啦，于是有啦算法二。
算法二：
#include
using namespace std;
int find_maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int find_maxsun2(int*a, int n){
int i, j, newsum = 0, maxsum= 0;
for (i = 0; i newsum = 0;
for (j = i; j newsum += a[j]; /*每一次在j-1条件下更新newsum*/
if (newsum>maxsum) /*更新maxsum*/
maxsum = newsum;
}
}
return maxsum;
}
这个算法比1聪明，算法复杂度是o(n2)，显然还不是我们想要的复杂度。
算法三：
算法三使用的是分治法的思想，基本思想不言而喻先分后治，将问题分解为小问题然后在可以总和小问题来解决，我们把原序列一分为二，那么最大子序列在左边，在右边，或者跨越边界，基本思路如下：
第一步：将原序列一分为二，分成左序列和右序列。
第二步：递归求出子序列s左和s右。
第三部：从中分线向两边扫描，找出跨越中线的最大子序列和s中。
第四步：求得s=max{s左，s中，s右}；
代码实现如下：
#include
using namespace std;
int find_maxsum3(int*a,int low,int high);
int max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int find_maxsum3(int*a,int low,int high){
int maxsum = 0, midsum, leftsum, rightsum,i;
midsum = 0;
if (low == high){ /*递归的终止条件*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low + high) / 2; //找到分的中点
leftsum = find_maxsum3(a, low, mid); /*递归找到左边序列最大和*/
rightsum = find_maxsum3(a, mid + 1, high); /*递归找到右边序列最大子序列和*/
/*然后可以求中间跨越边界序列的最大和*/
int newleft = 0,max_borderleft=0, newright = 0,max_borderright=0;
for (i = mid; i >= low; i--){ /*向左扫描找到最大和*/
newleft += a[i];
if (newleft > max_borderleft)
max_borderleft = newleft;
}
for (i = mid + 1; i newright+=a[i];
if (newright >= max_borderright)
max_borderright = newright;
}
midsum = max_borderright + max_borderleft;
return max(leftsum, midsum, rightsum); /*返回治的结果*/
}
int max(int a, int b, int c){    /*找出3者中最大的数*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= b&&c>=a)
return c;
}
我们来算一算这个算法时间复杂度：
t(1)=1;
t(n)=2t(n/2)+o(n);
=2kt(n/2k)+ko(n)=2kt(1)+ko(n)（其中n=2k）=n+nlogn=o(nlogn);
虽然这个算法已经非常好啦，但是并不是最快的算法。
算法四：
算法四叫做在线处理。意思为，每读入一个数据就进行及时处理，得到的结果是对于当前读入的数据都成立，即为在任何位置终止读入，算法都可以给出正确的解，边读边解。
#include
using namespace std;
int find_maxsum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int find_maxsum4(int*a, int n){
int i, newsum = 0, maxsum = 0;
for (i = 0; i newsum += a[i]; /*当前子序列和*/
if (maxsum maxsum = newsum; /*更新最大子序列和*/
if (newsum newsum = 0;
}
return maxsum;
}
这种算法是将读入的数据一个个扫描一遍，只有一个for循环，解决同一个问题算法差别大，在于一个窍门，让计算机记住一些关键的中间结果，避免重复计算。
以上就介绍了最大子序列和算法分析，包括了方面的内容，希望对php教程有兴趣的朋友有所帮助。