算法复杂度，从开始学习算法分析之后就一直在讨论着这个问题，很多人都认为，计算机相关人才只是“高级蓝领”，“技术民工”，那为什么计算机的大牛们依然乐此不疲呢？我想，是因为他们发现了思考的乐趣。
有时候，稍加思考，你所做的事情就会变得格外的美妙，有时候，更简短的代码带来的却是更高的执行效率，生活，恰是需要这样的点睛之笔。
好了，前奏铺垫的有点长，下面进入正题，通过对大家所熟知的一道题的分析，最大子序列和的问题，让我们来初步感受一下编程的美丽：
题目是这样描述的，给定指定的整数序列（可能是负数）A1，A2…..An,寻找（并标识）使得Ai至Aj的连续的和值最大的子序列。
首先初步分析一下，假设输入的是1,3,-5,6,-3这五个数，那么最大的明显是1，3，-5,6所组成的子序列，包含四项，数组下标从0开始，到3为止。而对于一个全为负数的序列，最长公共子序列的和值应该是0，理由在于，由0个整数所组成的空子序列也是一个子序列。
问题分析到这里，大家应该对问题有了初步了解了，那么对于一道寻值的问题，我们一般第一反应所想到的恐怕就是“暴力求解”了，将每一个可能的子序列都找出来，然后一一比对，比如一个长度为6的序列，他的子序列的长度就有0到6这7种大情况，再把每一种情况细分(如长度为3的子序列，数组的下标索引可以是0,1,2,3),把所有的情况都列出来，这样毫无疑问是可以找到答案的，通过这样的分析，我们的O(N^3)的算法就出炉了，如下：
Java代码
/**
* O(N^3)算法
* @return 最大公共子序列的和
*/
public int maxSubsequenceSum1(int a[]){
int maxSum=0;
for(int i=0;i<a.length;i++){
for(int j=i;j<a.length;j++){
int thisSum=0;
for(int k=i;k<=j;k++){
thisSum+=a[k];
if(thisSum>maxSum){
maxSum=thisSum;
seqStart=i;//最大公共子序列索引的起始坐标
seqEnd=j;//最大公共子序列索引的末尾坐标
}
}
}
}
System.out.println(seqStart);
System.out.println(seqEnd);
return maxSum;
}
不难看出，这个算法的运行时间完全由最内层的for循环决定，而里层执行的次数正好等于满足1<=i<=k<=j<=N的有序三元组（i,j,k）的个数，大家可以自己用数学公式证明一下，这个有序三元组的个数是N(N+1)(N+2)/6。这种“暴力求解”的优点是，编码非常简单，理解起来也很容易，算法越简单就越容易正确地编程实现。不过这样的方法很明显效率偏低，三层嵌套因此导致算法的复杂度是立方级的，不过我们要注意的是，三个连续的循环表现出的是线性行为，也就是说，不是简单的N*N*N的算法。那么我们是不是可以去掉一个循环来提高程序的执行效率呢？请看以下分析：
很明显，上面的算法有很多不必要的计算，假设我们已经计算出了i,…,j-1的和，那么计算子序列i,…j的和是不是很简单呢？只需要再进行一次计算。立方算法恰恰就丢掉了这一个信息，如下的改进算法，使用的是两个而不是三个循环嵌套：
Java代码
/**
* O(N^2)算法
*/
public int maxSubsequenceSum2(int a[]){
int maxSum=0;
for(int i=0;i<a.length;i++){
int thisSum=0;
for(int j=i;j<a.length;j++){
thisSum+=a[j];
if(thisSum>maxSum){
maxSum=thisSum;
seqStart=i;
seqEnd=j;
}
}
}
System.out.println(seqStart);
System.out.println(seqEnd);
return maxSum;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 问题
， 分析
， 序列
， 下标
， 所有公共子序列
， 长公共子字符串
， 子序列
， 最大
最大子序列
最大子序列和联机算法、线性最大流算法、线性回归算法、双线性插值算法、时间序列算法，以便于您获取更多的相关知识。