学向勤中得,萤窗万卷书。这篇文章主要讲述算法题每日一练---第36天:连续子数组的最大和相关的知识,希望能为你提供帮助。
一、问题描述输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
题目链接:连续子数组的最大和
二、题目要求要求:
- 1 < = arr.length < = 10^5
- -100 < = arr[i] < = 100
- 要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
考察
1.动态规划中等题型
2.建议用时5~15min
三、问题分析这也是一道比较典型的动态规划问题,动态规划没做过的可以看这一篇入门题解:
算法题每日一练---第34天: 青蛙跳台阶
还是用我们的三步走老套路:
第一步含义搞懂:
这一题在力扣上面是简单题,但我第一次做想了半天要怎么往动态规划上面靠拢,瞬间觉得这一题不简单。
文章图片
先看题目要求是什么,求出数组中连续子数组的最大值,下面就以示例里面的值讲解。
设一维数组dp[i]就代表从区间1~i的范围里面,以num[i]结尾的连续子数组最大值。
第二步变量初始:
这一题我们只需要初始一个变量就行,那就是dp[0]=nums[0]
第三步规律归纳:
这一步就是最关键的一步了,能不能娶上媳妇就看最后一哆嗦了。
我先把nums数组和dp数组里面的值列举一下,看看能不能发现规律:
文章图片
仔细看一下,每一个dp[i]是如何得到的,是不是当前位的num[i]加上前面一个dp[i-1]数又或是没加,那没加是因为前面的数是负的嘛。所以,规律出现:
文章图片
三步走,打完收工!
四、编码实现【算法题每日一练---第36天(连续子数组的最大和)】```c++
#include< iostream>
using namespace std;
int main()
long long int i,n,dp[100005],nums[100005],max; //初始化变量
cin> > n; //输入数组大小
for(i=0; i< n; i++)
cin> > nums[i]; //输入数组数据
max=dp[0]=nums[0]; //变量初始
for(i=1; i< n; i++)//循环判断
if(dp[i-1]< =0)//负数是本身
dp[i]=nums[i];
else
dp[i]=nums[i]+dp[i-1]; //正数加上上一个
if(dp[i]> max)//是否大于当前max
max=dp[i];
cout< < max; //输出结果
return 0;
## 五、测试结果![3.png](https://s4.51cto.com/images/blog/202204/29093503_626b40c7b059674598.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)
推荐阅读
- Cilium v1.10.6 安装部署
- 云原生时代的搜索服务算力管理
- javaScript中Math内置对象基本方法入门
- Redis 的编译安装及多种方式启动
- Selenium自动化应该避免的测试场景
- python 包之 blinker 信号库教程
- 王道考研|笔记&补充线性表之顺序表
- K8S关于pod资源监控
- 带你了解Go语言基础之切片