`
cq520
  • 浏览: 166619 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

最大子序列和问题从O(N^3)到线性的算法

阅读更多

       算法复杂度,从开始学习算法分析之后就一直在讨论着这个问题,很多人都认为,计算机相关人才只是“高级蓝领”,“技术民工”,那为什么计算机的大牛们依然乐此不疲呢?我想,是因为他们发现了思考的乐趣。

       有时候,稍加思考,你所做的事情就会变得格外的美妙,有时候,更简短的代码带来的却是更高的执行效率,生活,恰是需要这样的点睛之笔。

       好了,前奏铺垫的有点长,下面进入正题,通过对大家所熟知的一道题的分析,最大子序列和的问题,让我们来初步感受一下编程的美丽:

       题目是这样描述的,给定指定的整数序列(可能是负数)A1A2…..An,寻找(并标识)使得AiAj的连续的和值最大的子序列。

       首先初步分析一下,假设输入的是1,3,-5,6,-3这五个数,那么最大的明显是13-5,6所组成的子序列,包含四项,数组下标从0开始,到3为止。而对于一个全为负数的序列,最长公共子序列的和值应该是0,理由在于,由0个整数所组成的空子序列也是一个子序列。

       问题分析到这里,大家应该对问题有了初步了解了,那么对于一道寻值的问题,我们一般第一反应所想到的恐怕就是“暴力求解”了,将每一个可能的子序列都找出来,然后一一比对,比如一个长度为6的序列,他的子序列的长度就有067种大情况,再把每一种情况细分(如长度为3的子序列,数组的下标索引可以是0,1,2,3),把所有的情况都列出来,这样毫无疑问是可以找到答案的,通过这样的分析,我们的O(N^3)的算法就出炉了,如下:

      

/**
* 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的和是不是很简单呢?只需要再进行一次计算。立方算法恰恰就丢掉了这一个信息,如下的改进算法,使用的是两个而不是三个循环嵌套:

 

/**
 * 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;
} 

       很多人可能做到上面一步就停止了,我们已经完成了从N^3N^2的飞跃,那么是不是还可以删除一个循环来达到线性算法呢?想法是美妙的,但是具体实施起来却没有那么简单。假设Ai,j是满足Si,j<0的第一个子序列,如下图(图画的不好,请见谅):

      

       容易证明,在假设的情况下,如果q>j,那么Ai,q不是最大连续子序列,因为序列的索引完全可以从下一个大于0的数开始。所以当我们得到了第一个小于0的子序列之后,完全可以从这个序列里面跳出来,继续计算接下来的序列段,避免重复的计算,那么这一次的算法就需要大家仔细的思考一下了,下面给出一种方法:

       

/**
 * 线性算法
 */
public int maxSubsequenceSum3(int a[]){
	int maxSum=0;
	int thisSum=0;
	for(int i=0,j=0;j<a.length;j++){
		thisSum+=a[j];
		if(thisSum>maxSum){
			maxSum=thisSum;
			seqStart=i;
			seqEnd=j;
		}
		else if(thisSum<0){
			thisSum=0;
			i=j+1;
		}
	}
	System.out.println(seqStart);
	System.out.println(seqEnd);
	return maxSum;
}

 

       虽然这种算法通过跳过不可能的条件而达到了更高的效率,不过,相比“暴力求解”来说,正确性就没那么明显了,相反,其中的很多条件都需要我们证明,我们已经通过一个简单的数学运算证明了它的正确性。数学将我们带入了编程的世界,又为我们提供了坚实的基础。编程其实很多时候不是方法的照搬,通过思考,我们能够得到更优的方法,就像我们热爱探索世界的眼睛。

       走进编程的世界,感受编程之美吧。

 

  • 大小: 17.7 KB
分享到:
评论

相关推荐

    最大子序列之和C++实现常数时间

    通常,最大子序列和问题通过 Kadane's Algorithm(卡丹算法)可以在线性时间内O(n)解决,但实现常数时间的解决方案则需要特别的优化。然而,应该注意的是,对于大多数情况,常数时间复杂度是不现实的,因为至少需要...

    C++算法-最大子序列和.zip

    本资料包“C++算法-最大子序列和.zip”聚焦于C++实现的一种经典算法——最大子序列和(Maximum Subarray Problem),这在数据结构与算法的学习中是非常关键的一环。 最大子序列和问题是一个寻找一串数组中具有最大...

    最大子序列和问题的求解.md

    ### 最大子序列和问题详解 #### 一、引言 最大子序列和问题是一个经典的计算机科学问题,涉及在一串整数(其中可能包括负数)中找到具有最大和的连续子序列。此问题不仅在理论研究中有重要意义,在实际应用如生物...

    算法-动态规划- 线性 DP- 最大和问题(包含源程序).rar

    在解决最大子序列和问题时,我们可以定义一个二维数组`dp`,其中`dp[i]`表示以第`i`个元素结尾的最大子序列和。初始时,`dp[0]`等于数组的第一个元素。对于后续的每个元素,我们有两种选择:不包括它,或者包括它。...

    第一次算法初步.pdf

    暴力枚举的时间复杂度为O(n^3),优化枚举通过减少一层循环降低到O(n^2),而贪心法则只需O(n)的时间复杂度,通过每次累加当前元素并更新最大子数组和,当和变为负数时清零重新开始。 作业题1设计一个队列,要求支持...

    java算法大全源码包

    - 最大子序列和问题:Kadane's algorithm。 6. **贪心算法**: - 银行家算法:用于避免系统死锁。 - Kruskal's和Prim's算法:用于求最小生成树。 7. **递归与回溯**: - 数独解决方案:深度优先搜索的典型应用...

    ACM编程题模板和各种经典算法数据结构实现代码

    - 最长有序子序列问题包括最长递增子序列和最长递减子序列等。 16. **最长公共子序列** - 最长公共子序列问题是指在两个或多个序列中找到最长的公共子序列。 17. **最少找硬币问题(贪心策略-深搜实现)** - ...

    程序员面试算法设计解析

    11. **滑动窗口**:滑动窗口是处理数组或序列中连续子集问题的有效方法,如寻找子数组最大和、最大子序列和等。 通过深入学习以上知识点,并结合实际编程练习,程序员可以在面试中展现出扎实的算法基础和优秀的解决...

    求最大子序的4种算法

    将序列分为两部分,分别找出两部分的最大子序列和,然后考虑跨越分界线的子序列。不过,这种方法的效率不如动态规划高。 线性扫描法(Linear Scan)实质上就是Kadane's algorithm,这是一种非常高效且简洁的解决...

    算法导论第三版_英文版

    动态规划的关键在于找出重叠子问题和最优子结构性质。 #### 三、函数的增长 ##### 3.1 渐进记号 渐进记号是用来描述函数增长速度的数学工具,主要包括大O记号、小o记号、Ω记号、θ记号和ω记号。这些记号帮助我们...

    常用算法类常用算法类常用算法类

    - 最大子序列和问题:求解一个数列中连续子序列的最大和,例如Kadane's algorithm。 4. 回溯法: - N皇后问题:在N×N棋盘上放置N个皇后,使其互不攻击。 - 字符串排列:找出字符串的所有可能排列。 - 图论问题...

    计算机算法设计与分析练习题.docx

    3. 使用线性时间选择算法,例如Median of Medians算法,可以在O(n)时间内找到带权中位数。 4. 邮局位置问题,带权中位数是最优解,最小化所有点到中位数的距离之和。 三.磁带存储问题 1. 贪心策略按程序长度非降序...

    算法设计与分析(王晓东编).rar

    3. **分治策略**:这是一种重要的算法设计策略,例如在解决最大子序列和、快速排序等问题时应用。 4. **动态规划**:用于解决最优化问题,如背包问题、最长公共子序列、斐波那契数列等,动态规划的核心是状态转移...

    很好的算法设计与分析电子教案

    3. **排序与搜索算法**:常见的排序算法如冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序,以及线性搜索、二分搜索等,都会被详细讲解。这些算法不仅理论性强,而且在实际编程中应用广泛。 4. **图算法...

    VB程序设计常用算法

    - 最大子序列和问题:寻找数组中连续子序列的最大和,Kadane's算法是解决此类问题的经典方法。 4. 回溯法: - 数独解决方案:通过尝试填充空格并回溯到上一步来解决数独问题。 - 八皇后问题:在棋盘上放置八个...

    C常用算法程序集.rar

    - 最大子序列和问题:Kadane's algorithm,找到数组中连续子序列的最大和。 4. 图论算法: - 广度优先搜索(BFS):用于查找树或图的最短路径,或者解决层次遍历问题。 - 深度优先搜索(DFS):遍历图的所有可能...

    JAVA近百种算法大全打包.rar_V4M_算法

    3. 最大子序列和问题:例如Kadane's算法求解一个数组中连续子序列的最大和。 五、贪心算法 贪心算法在每一步选择中都采取在当前状态下最好或最优的选择,但并不保证得到全局最优解。 例子:霍夫曼编码,每次合并两...

Global site tag (gtag.js) - Google Analytics