❤️博客主页：小镇敲码人
🍏 欢迎关注：👍点赞 👂🏽留言 😍收藏
🌞勤奋努力是一个长期的过程，如果追求速成，就是异想天开。你越努力、越认真生活，生活就会变得越美丽。如果一直保持奋斗，你的人生将会发生翻天覆地的变化。
🍉 如果你也迷失在了路上，对人生充满了迷惘，不要害怕，冷静下来，慢慢的自救，不断求知，让自己变得更加优秀吧！！！😃😃😃
一、题目
老规矩，给出牛客网原题链接，感兴趣的小伙伴可以去做一下，虽然是简单题，但事情总是从难到易的嘛点击此处跳转
给定一个长度为 n 的数组，数组中的数为整数。 请你选择一个非空连续子数组
， 使该子数组所有数之和尽可能大，子数组最小长度为1。求这个子数组最大值。
二、题解
2.1动态规划
1.定义dp[i]为尾项为a[i]的连续子数组的最大和
2.那么可以得到递推式：dp[i] = Max(dp[i-1]+a[i],a[i])
注意：dp[i]在(dp[i-1]+a[i])和a[i]两者中取一个较大值，恰好完美的保证了dp[i]是尾项为a[i]的连续子数组的最大和
那为什么说它保证了连续呢，因为按照定义dp[i-1]也是连续的。
3.得到了递推式就很简单了，利用递归和递推都可以实现
这里对于首项和尾项给出一个定义，如图所示
2.2贪心算法
2.1.1 贪心算法的定义
首先我们得先了解一下什么叫做贪心，我的理解是这样的：选择对当前而言最优的一个解，从而能达到整体最优，什么意思呢？
举几个例子来说明一下吧：
1.动物世界中，蟒蛇吃鳄鱼时，蟒蛇不会一口吃下去，而是一点一点的吃，这样一次看起来只吃了一点点，但整体看上去蟒蛇最终还是把鳄鱼吃完了。
但要注意贪心思维并不适用所有的场景，比如下面生活中的实例
2.有些人常说，人生苦短，要及时行乐所以每一次面临抉择时都会选择让自己更舒服的一个方案，这虽然看起来局部上面好像是开心了，但以大局观去看，整体上并不是最优的，例如小帅是一个喜欢快乐的男生，他总是喜欢打游戏到深更半夜，父母非常苦恼，但当父母说他时，他总回答：“哎呀，人生苦短，要及时行乐嘛”，对此父母也不好说什么，其实这就是小帅陷入贪心思维，只顾眼前，但长期之后身体反而会出现问题，这便是局部最优没有造成整体最优😁😁
理解了什么是贪心算法，我们还要知道它的两个性质
2.2.2贪心算法的性质
贪心算法求解具有两个重要的性质:贪心选择性质和最优子结构性质。
(1)贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心法与动态规划法的主要区别。
(2)最优子结构性质
该问题解的整体最优性依赖于其局部子问题解的最优性这种性质是可以采用贪心算法解决问题的关键特征。
举例:如最小生成树求解。
2.2.3本题的贪心算法解决思路
1.定义一个sum，它表示遍历到以ai为尾项时的一个连续子数组的局部最优解，且sum必须要大于0，因为只有这样对于a[i]来说，当以它为尾项时那个连续子数组的值才是最优的。
2.sum = Max（0,sum+a[i]）,可以看到如果sum的初始值设为sum = Max（0，a[0]）,那么sum >= 0,对于a[i]来说，当它为尾项时，就可以一直保证局部最优了。
3.创建一个变量ret，因为在遍历时，sum+a[i]可能是小于0的，那我们怎样确定这些局部最优里面，谁才是最优的呢，这个时候我们的ret变量就可以起到一个维护最大值的作用。
2.2.4贪心与动态规划的区别
我的理解是它们有一下几点区别：
1️⃣解决的问题不同：
贪心算法重点的问题是否做到了局部最优，它通常对后面的问题的影响是可估计的，而动态规划则是把一个很大的问题分成很多子问题去求
2️⃣ 能否获得最优解：
贪心算法可能会得不到最优解，但动态规划一定可以得到最优解
3️⃣算法复杂度不同：
通常动态规划的时间复杂度和空间复杂度都会比贪心算法的要大。具体大家可以看看这篇文章点击此处直接跳转—>动态规划与贪心的区别
三、代码实现
3.1法一：动态规划(递归实现)法
3.1.1创建变量n，并读入数据
int n = 0;
scanf("%d",&n);
3.1.2创建动态数组
int* a = (int*)malloc(n * sizeof(int));//创建动态数组a存储数据
int*dp = (int*)malloc((n+1) * sizeof(int));//创建动态数组dp用来存储是以a[i]为尾项的连续数组最大值
3.1.3对动态数组进行断言，并赋初值
assert(dp && a);//断言a和dp，防止空间申请不成功出现空指针的情况
memset(a, 0, (n * sizeof(int));
dp[0] = -1e9;//特殊情况i == 0将dp[0]设置的很小，便于我们得
//出dp[i]的首项，这一点后面也会有说明，看
//不懂先不要着急，且听我慢慢道来
3.1.4读入数据
/*！！！注意i从1开始，因为递推式
中存在dp[i-1],防止数组越界*/
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
3.1.5创建递归函数
summax(n, n, a, dp);
3.1.5.1实现递归函数
int summax(int n, int i, int* a, int* dp) {
if (i == 1)
return dp[i] = max(dp[i - 1] + a[i], a[i]);
return dp[i] = max(summax(n, i - 1, a, dp) + a[i], a[i]);
}
注意这里的i == 1的情况也正照应了我们为什么要将dp[0]设置的很小，是因为我们的数组下标是从1开始存入数据的，防止数组越界，而dp[1] = a[1],所以将dp[0]设置的很小，其实这里像下面那样改就没有这么多事了，但没办法我这该死的仪式感😆😆
int summax(int n, int i, int* a, int* dp) {
if (i == 1)
return dp[i] = a[i];
return dp[i] = max(summax(n, i - 1, a, dp) + a[i], a[i]);
}
3.1.6将动态数组排序
这里我们调用了一下快排函数需要引用头文件<stdlib.h>,并且需要自己实现一下比较器，这里我们一起给出，那什么是比较器呢？后续我们会出一期来专门介绍，大家可以先自行查阅资料
/* 下面是一个比较器
被快排函数用作比较，（a-b）> 0交换顺序
所以是一个升序的排序 */
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
qsort(dp, n + 1, sizeof(int), cmp);//升序排序最后一项为最大值
3.1.7打印结果
printf("%d", dp[n]);
return 0;
3.1.8完整C语言代码
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
/*
下面是一个比较器
被快排函数用作比较，（a-b）> 0交换顺序
所以是一个升序的排序
*/
int cmp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
/*
判断a,b的大小并
返回较大的值
*/
int max(int a, int b) {
if (a > b)
return a;
return b;
}
int summax(int n, int i, int* a, int* dp) {
if (i == 1)
return dp[i] = max(dp[i - 1] + a[i], a[i]);
return dp[i] = max(summax(n, i - 1, a, dp) + a[i], a[i]);
}
int main() {
int n = 0;
scanf("%d", &n);
int* a = (int*)malloc(n * sizeof(int));
int* dp = (int*)malloc((n + 1) * sizeof(int));
assert(a && dp);//断言防止动态数组空间申请不成功
memset(a, 0, (n + 1)* sizeof(int));
dp[0] = -1e9;//特殊情况i == 0将dp[0]设置的很小，便于我们得出dp[i]的首项
/*将数据存入
动态数组a中*/
/*！！！注意i从1开始，因为递推式
中存在dp[i-1],防止数组越界*/
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
summax(n, n, a, dp);//注意i传的值，这是与思路二递归的区别之一
qsort(dp, n + 1, sizeof(int), cmp);//升序排序最后一项为最大值
printf("%d", dp[n]);
return 0;
}
3.2法二：贪心
前几步创建变量的步骤基本与法一相同，这里我们不再做过多的叙述
注意由于我们的sum只接受大于0的数，当给的数据全为负数时，我们的贪心就失效了，所以要特判一下全为负数的情况
3.2.1创建标志变量并录入数据
注意标志变量flag用来判断数据是否全为负数文章来源：https://www.toymoban.com/news/detail-473530.html
int flag = 0;//标记全是负数的情况
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if (a[i] >= 0)
flag = 1;
}
3.2.2考虑全部为负数的情况
if (!flag)
{
int ret = a[0];
/*求出负数里面的较大值*/
for (int i = 1; i < n; i++)
{
ret = Max(ret, a[i]);
}
printf("%d", ret);
return 0;//提前结束main函数防止其继续进行下去
}
3.2.3考虑不全为负数的情况
int ret = 0;//初始化ret和sum的值
int sum = 0;
for(int i = 0;i < n;i++)
{
sum = Max(0,sum+a[i]);//只要sum的值大于0，对于当前的a[i]，就是最优的，即以a[i]为尾项的连续子数组之和的最大值，
// 反之，sum<0,我们需将sum重置为0，因为这会对后面的值产生影响，从而得不到局部最优
ret = Max(ret,sum);//从局部最优解里面选出一个整体最优解，这就是我们需要的答案
}
3.2.4打印最优解
printf("%d",ret);
3.2.5实现求最大值函数Max
/*
返回较大值
*/
int Max(int a, int b) {
if (a > b)
return a;
return b;
}
3.2.6C语言完整代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/*
返回较大值
*/
int Max(int a, int b) {
if (a > b)
return a;
return b;
}
int main() {
int n = 0;
scanf("%d", &n);
int* a = (int*)malloc(n * sizeof(int));//创建一个动态数组来存储数据
assert(a);//对指针a进行断言，防止出现空指针的情况
int flag = 0;//标记全是负数的情况
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
if (a[i] >= 0) flag = 1;
}
/*
全为负数的情况
*/
if (!flag) {
int ret = a[0];
/*求出负数
里面的较大值*/
for (int i = 1; i < n; i++) {
ret = Max(ret, a[i]);
}
printf("%d", ret);
return 0;//提前结束main函数防止其继续进行下去
}
int ret = 0; //将ret和sum的值初始化
int sum = 0;
/*
不全为负数的情况
*/
for (int i = 1; i < n; i++) {
sum = Max(0, sum +a[i]);//只要sum的值大于0，对于当前的a[i]，就是最优的，即以a[i]为尾项的连续子数组之和的最大值，
// 反之，sum<0,我们需将sum重置为0，因为这会对后面的值产生影响，从而得不到局部最优
ret = Max(ret,sum);//从局部最优解里面选出一个整体最优解，这就是我们需要的答案
}
printf("%d", ret);//打印这个整体最优解
return 0;
}
四、总结与思考
这上面的两种方法还有不同的实现方式，比如法一的动态规划，就可以用递推的方式，这样可以节省o（n）的额外空间，法二用贪心的思维去解，也节省了空间,这便是贪心的优势所在，另外提一嘴，这两种方法都可以反过来求，例如第一种动态规划的解法dp[i]如果定义为首项为a[i]的连续子数组的最大和一样是可以解决这个题目的，这里由于篇幅不再展开，最后本人才疏学浅，若对以上文章有任何疑问，欢迎大家在评论区与我讨论，或者私信交流都是可以的哦😘😘文章来源地址https://www.toymoban.com/news/detail-473530.html
到了这里，关于【动态规划】NK刷题记之DP6 连续子数组最大和（C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
