当前位置: 首页 > news >正文

[C++]四种方式求解最大子序列求和问题

问题

给定整数: A1,A2,,An
jk=iAk 的最大值(为方便起见,假设全部的整数均为负数,则最大子序列和为0)

比如

对于输入:-2,11,-4,13,-5,-2,答案为20,即从A2A4

分析

这个问题之所以有意思。是由于存在非常多求解它的算法。

解法一:穷举遍历

老老实实的穷举出全部的可能,代码例如以下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//计算并返回所最大子序列的和:穷举遍历
int maxSubSum1(const vector<int> & a)
{
	//用来存储最大子序列的和
	int maxSum = 0;

	//i标记子序列的头
	for (int i = 0; i < a.size(); i++)
	{
		//j标记子序列的尾
		for (int j = i; j < a.size(); j++)
		{
			//用来存储当前头尾计算的求和结果
			int thisSum = 0;

			//将子序列的值依次增加求和结果
			for (int k = i; k <= j; k++)
			{
				thisSum += a[k];
			}

			//存储两者的最大值
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}

这是大多数人都会想到的方法:把全部的可能都列举出来,然后再把子序列的全部值都加起来求和。
简单粗暴的攻克了问题。并且还非常好理解。


这样的算法的时间复杂度为O(N3)

解法二:穷举优化

事实上第三个for循环全然没有必要,在第二层for循环的时候就计算求得的和并且继续带入下一轮的for循环就可以:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//计算并返回所最大子序列的和:穷举优化
int maxSubSum2(const vector<int> & a)
{
	//用来存储最大子序列的和
	int maxSum = 0;

	//i标记子序列的头
	for (int i = 0; i < a.size(); i++)
	{
		//用来存储当前头尾计算的求和结果
		int thisSum = 0;

		//j标记子序列的尾
		for (int j = i; j < a.size(); j++)
		{

			//将子序列的值增加上次求和结果
			thisSum += a[j];

			//存储两者的最大值
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}

这样的算法的时间复杂度为O(N2)

解法三:分而治之

分而治之,顾名思义分为两个部分

  • 分:把大问题分成大致相等的两个子问题,然后递归的进行求解。
  • 治:把两个子问题的解合并到一起并再做少量的附加工作。

在最大子序列和的问题里,最大子序列的和可能出如今三个地方:

  • 整个出如今输入数据的左半部
  • 整个输入数据的右半部
  • 横跨左右两个部分

对于前两种能够递归求解,对于第三种,能够把左右两个部分的和分别求出,然后加在一起。
详细的代码例如以下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//计算并返回所最大子序列的和:分而治之
int maxSubSum3(const vector<int> & a,int left,int right)
{
	//基础情况:单个元素。直接返回这个数值或者0
	if(left == right)
	{
		return a[left];
	}

	//获取中点
	int center = (left + right) / 2;

	/* 整个出如今输入数据的左半部的最大子序列求和 */
	int leftMaxSum = maxSubSum3(a,left,center);

	/* 整个出如今输入数据的右半部的最大子序列求和 */
	int rightMaxSum = maxSubSum3(a,center+1,right);

	//计算左右两个子序列求和结果的最大值
	int lrMaxSum = max(leftMaxSum,rightMaxSum);


	/* 横跨左右两个部分的最大子序列求和 */

	//从center向左处理左半边
	int maxLeftSum = 0;
	int leftSum = 0;
	for (int i = center; i >= left; i--)
	{
		leftSum += a[i];
		maxLeftSum = max(maxLeftSum,leftSum);
	}

	//从center向右处理右半边
	int maxRightSum = 0;
	int rightSum = 0;
	for (int j = center+1; j <= right; j++)
	{
		rightSum += a[j];
		maxRightSum = max(maxRightSum,rightSum);
	}

	//返回求和和前面算出结果的最大值
	return max( lrMaxSum, maxLeftSum+maxRightSum);
}

这样的算法的时间复杂度为O(NlogN)

解法四:联机算法

先来解释一下联机算法的概念:

联机算法:在随意时刻,算法对要操作的数据仅仅读入(扫描)一次,一旦被读入并处理,它就不须要在被记忆了。而在此处理过程中算法能对它已经读入的数据马上给出对应子序列问题的正确答案。

具有这样的特性的算法叫做联机算法(on-line algorithm)。

对于这个问题。代码例如以下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//计算并返回所最大子序列的和:最优算法
int maxSubSum4(const vector<int> & a)
{
	//终于结果
	int maxSum = 0;
	//当前求和
	int nowSum = 0;

	//遍历序列的全部元素
	for (int j = 0; j < a.size(); j++)
	{
		//将当前元素增加到结果中
		nowSum += a[j];

		//假设大于最大值,则存储为新的最大值
		if(nowSum > maxSum)
			maxSum = nowSum;
		else if(nowSum < 0)
			nowSum = 0;
	}

	return maxSum;
}

这样的算法的时间复杂度为O(N)

总结

下表是统计的四种算法的运算结果:

输入大小O(N3)O(N2)O(NlogN)O(N)
N=100.0000090.0000040.0000060.000003
N=1000.0025800.0001090.0000450.000006
N=10002.2810130.0102030.0004850.000031
N=10000NA1.23290.0057120.000317
N=100000NA1350.0646180.003206

从表中能够看出,在数据量非常小的时候(在它小时候=.=)。算法在瞬间就完毕了。差距也不是非常明显。
可是随着输入量的增大,一些算法的弊端逐渐显现出来,效率低的甚至在有限的时间里算不出结果来。
对于非常多高效的算法来说,读取数据往往是解决这个问题的瓶颈,

相关文章:

  • libserialport: cross-platform library for accessing serial ports
  • Linux USB驱动框架分析(2)【转】
  • 安卓android.support.design使用中的问题
  • swift锁屏播放,音乐进度更新,专辑,歌手名显示
  • srxboys 今日说 !
  • windows 下将目录映射成盘符
  • ios自定义控件,使UIScrollView自己处理输入时键盘遮挡控件
  • 算法学习笔记——动态规划法
  • js 自定义方法 实现停留几秒 sleep
  • Global Azure SQL Server Database异地复制配置介绍
  • 练习JavaScript实现过滤特殊字符
  • jQuery Mobile_页面事件
  • struts2遍历map
  • java基础tips
  • 第一章 Java常用集合类总览
  • ➹使用webpack配置多页面应用(MPA)
  • AHK 中 = 和 == 等比较运算符的用法
  • android百种动画侧滑库、步骤视图、TextView效果、社交、搜房、K线图等源码
  • Bootstrap JS插件Alert源码分析
  • gulp 教程
  • java B2B2C 源码多租户电子商城系统-Kafka基本使用介绍
  • Java新版本的开发已正式进入轨道,版本号18.3
  • October CMS - 快速入门 9 Images And Galleries
  • React 快速上手 - 07 前端路由 react-router
  • Travix是如何部署应用程序到Kubernetes上的
  • 记录:CentOS7.2配置LNMP环境记录
  • 区块链分支循环
  • 说说动画卡顿的解决方案
  • 微信开源mars源码分析1—上层samples分析
  • 小程序上传图片到七牛云(支持多张上传,预览,删除)
  • 正则表达式
  • 走向全栈之MongoDB的使用
  • AI又要和人类“对打”,Deepmind宣布《星战Ⅱ》即将开始 ...
  • ​软考-高级-信息系统项目管理师教程 第四版【第14章-项目沟通管理-思维导图】​
  • ​一文看懂数据清洗:缺失值、异常值和重复值的处理
  • ###STL(标准模板库)
  • $.ajax()参数及用法
  • (10)STL算法之搜索(二) 二分查找
  • (C语言)球球大作战
  • (JSP)EL——优化登录界面,获取对象,获取数据
  • (附源码)springboot“微印象”在线打印预约系统 毕业设计 061642
  • (附源码)springboot建达集团公司平台 毕业设计 141538
  • (机器学习-深度学习快速入门)第一章第一节:Python环境和数据分析
  • (力扣)1314.矩阵区域和
  • (一)VirtualBox安装增强功能
  • (已解决)vue+element-ui实现个人中心,仿照原神
  • (原)本想说脏话,奈何已放下
  • .[backups@airmail.cc].faust勒索病毒的最新威胁:如何恢复您的数据?
  • .form文件_一篇文章学会文件上传
  • .NET CF命令行调试器MDbg入门(一)
  • .net CHARTING图表控件下载地址
  • .NET CLR基本术语
  • .net mvc actionresult 返回字符串_.NET架构师知识普及
  • .Net程序猿乐Android发展---(10)框架布局FrameLayout
  • .NET使用存储过程实现对数据库的增删改查