首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
子数组的最大累加和问题
[编程题]子数组的最大累加和问题
热度指数:2857
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 256M,其他语言512M
算法知识视频讲解
给定一个数组arr,返回子数组的最大累加和
例如,arr = [1, -2, 3, 5, -2, 6, -1],所有子数组中,[3, 5, -2, 6]可以累加出最大的和12,所以返回12.
[要求]
时间复杂度为
,空间复杂度为
输入描述:
第一行一个整数N。表示数组长度
接下来一行N个整数表示数组内的元素
输出描述:
输出一个整数表示答案
示例1
输入
7 1 -2 3 5 -2 6 -1
输出
12
备注:
马上挑战
算法知识视频讲解
提交运行
算法知识视频讲解
添加笔记
求解答(4)
邀请回答
收藏(24)
分享
纠错
提交结果有问题?
16个回答
3篇题解
开通博客
九皋凤鸣
发表于 2021-11-25 06:49:51
思路: 如果某段累加和<0, 则对后续累加无(正)贡献, 需终止本段累加,重启新累加; 求多段累加和的最大值。 步骤: 累加: 从左到右,累加; 控制: α.累加和>0,继续累加; β.累加和<0, a、终止本轮累加; b、max(当前累加和最值,本次累加之前的和) c
展开全文
快支棱起来的椰子很愤怒
发表于 2022-01-12 16:12:28
n = int(input()) nums = list(map(int, input().split())) before = nums[0] res = nums[0] for i in range(1, n): before = max(nums[i], nums[i] + befor
展开全文
瓜瓜请多指教
发表于 2020-07-21 16:49:19
include <bits/stdc++.h> using namespace std; int main(){ int N; cin>>N; vector<int> arr(N); for(int i=0;i<N;i++)
展开全文
问题信息
动态规划
上传者:
小小
难度:
16条回答
24收藏
2523浏览
热门推荐
通过挑战的用户
查看代码
小蔡先生a
2023-02-27 17:10:21
我不懂但是我大受震撼
2023-02-27 16:39:51
UchihaM...
2023-01-05 23:11:22
牛客66216...
2022-12-13 19:41:27
牛客71239...
2022-11-22 12:35:09
相关试题
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
未来工作城市的选择是怎样的?
通用能力
评论
(1)
你说在销售运营这个岗位上会涉及到一...
评论
(1)
相关性分析有哪些?
评论
(1)
如何检验聚类分析结果
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
7 1 -2 3 5 -2 6 -1
12