当前位置:首页>引流推广>最大子段和问题什么意思(最大子段和动态规划)

最大子段和问题什么意思(最大子段和动态规划)

从今天开始呢,我们就正式开始数据结构的学习了,可以说,这是计算机专业中最为核心的一门课程,也是最为重要的一块内容。 这一部分,是企业招聘时最为看重的一部分,也是大家解决算法实现逻辑最为重要的一部分,更是帮助大家找到一份好工作的重要筹码。 我们今天的这道题呢,就是解决“最大子列和问题”。 给定K个整数组成的序列{N1,N2,...,NK},“连续子列”被定义为{Ni,Ni+1,...,Nj},其中1...

从今天开始呢,我们就正式开始数据结构的学习了,可以说,这是计算机专业中最为核心的一门课程,也是最为重要的一块内容。

这一部分,是企业招聘时最为看重的一部分,也是大家解决算法实现逻辑最为重要的一部分,更是帮助大家找到一份好工作的重要筹码。

我们今天的这道题呢,就是解决“最大子列和问题”。

给定K个整数组成的序列{N1,N2,…,NK},“连续子列”被定义为{Ni,Ni+1,…,Nj},其中1<=i<j<K,而“最大子列和”则是找到一个所有连续子列元素的和中的最大值。

比方说给定一组序列为{-2,11,-4,13,-5,-2},其中连续子序列{11,-4,13}则是最大值为20。

那么最终打印输出的结果则为20。

最大子段和问题什么意思(最大子段和动态规划)

梳理逻辑

对于函数题,特别是解决数据结构与算法题的时候,一定要静下心来,然后梳理清楚题目的逻辑,当然了,现在不太会也很正常,完全可以慢慢来,但是如果要找工作的话,那可得加把劲了。

1、输入第一行给出正整数K(<=100000),用到一个scanf函数来输入。

2、第二行给出K个整数,因为我们是一个序列,所以用到的是数组。

3、最麻烦的则是找出最大和的子序列,我们可以这样来理解:

先从数组中的第一个元素开始加起,找到包含第一个元素的所有子序列的和,并比较大小。

然后找出最大值的和,记录下来。

与此同时,下一次循环遍历的时候就把这个和清零,但是最大值不变。

依次继续求和,并与最大值比较大小,记录下相对较大的那个值。

在所有循环都结束后,最终的那个最大值则是我们要求的最大值。

最大子段和问题什么意思(最大子段和动态规划)

代码实现

//最大子列和问题
#include<stdio.h>
int main(){
	int K;//给出正整数K
	int M[100000];//给出K个整数
	int count;//计数法
	int SUM = 0;//遍历求和
	int MAX = 0;//初始的最大值为0
	scanf(\"%d\", &K);
	for(int i=0;i<K;i++){
		scanf(\"%d\",&M[i]);
		if(M[i]<0){
			count++;
		}
	}
	if(count==K){//所有的数都是0的情况下
		printf(\"0\");
	}
	for(int i = 0; i < K; i++){
		//从元素1开始
		SUM = 0;//每次循环求和的时候,求和都要变为0才行
		for(int j = i; j < K; j++){
			SUM = SUM + M[j];
			if(SUM > MAX){
				MAX = SUM;
			}
		}
	}
	printf(\"%d\",MAX);

}

结果测试

最大子段和问题什么意思(最大子段和动态规划)最大子段和问题什么意思(最大子段和动态规划)

总结

这道数据结构题,可以说是数据结构章节中最为简单的一道题目了,有难度的还在后面呢,我研究生快毕业了,也知道自己得快速提升实力了,秋招末班车以及春招开启,一定要赶上,冲!!!

给TA打赏
共{{data.count}}人
人已打赏
引流推广

bmp是什么格式的文件怎么打开(在手机上照片jpg转换bmp的方法)

2022-4-12 10:38:53

引流推广

scratch游戏脚本大全(scratch简易小游戏教程)

2022-4-12 10:38:56

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索