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

最大子段和问题什么意思_最大子段和动态规划 从今天开始呢，我们就正式开始数据结构的学习了，可以说，这是计算机专业中最为核心的一门课程，也是最为重要的一块内容。

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

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

给定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;//给出正整数Kint M[100000];//给出K个整数int count;//计数法int SUM = 0;//遍历求和int MAX = 0;//初始的最大值为0scanf("%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);}结果测试总结这道数据结构题，可以说是数据结构章节中最为简单的一道题目了，有难度的还在后面呢，我研究生快毕业了，也知道自己得快速提升实力了，秋招末班车以及春招开启，一定要赶上，冲！！！