我要招人

去企业版

首页 > 试题广场 >

连续子数组的最大和

[编程题]连续子数组的最大和

热度指数：648748 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

$1 <= n <= 2\times10^5$

$-100 <= a[i] <= 100$

要求:时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$

进阶:时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$

示例1

输入

[1,-2,3,10,-4,7,2,-5]

输出

说明

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入

[2]

输出

示例3

输入

[-10]

输出

-10

算法知识视频讲解

leaves0924

发表于 2021-06-23 16:01:57

精华题解题目描述输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).示例1输入：[1,-2,3,10,-4,7,2,-5]返回值：18说明：输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10 展开全文

GhostLX

发表于 2021-06-18 21:30:33

精华题解题目陈述题目大意：给定一个有正数有负数的数组，求解连续的一段的元素的和的最大值算法1：暴力做法算法思路枚举左右端点，然后计算这个区间的总和now，跟ans比较，如果比ans大，则更新ans，最后循环结束返回ans 时间复杂度，空间复杂度代码实现 class Solution { pub 展开全文

牛客题解官

发表于 2022-04-22 12:47:05

精华题解题目主要信息：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组的和不存在空数组，−100<=a[i]<=100-100<=a[i]<=100−100<=a[i]<=100 举一反三：本题是动态展开全文

Peterliang

发表于 2021-06-23 00:36:33

精华题解题意分析给出一个数组序列，找出和最大的连续子数组的和。并且要求时间复杂度O(n)（由于这个题目比较简单，所以我们重点放在如何解题上面）考点是差分前缀和，下面大家可以结合下面这个图来更好地理解什么是差分思想，其实这只是一个很基础的一个差分，差分思想还是很重要的，可以帮助我们更好地优化我们的代码。展开全文

蒙牛麦片

发表于 2021-06-24 09:54:46

精华题解 jz30 连续子数组的最大和题意分析找出数组中连续部分的最大和。示例输入：input = [1,-2,3,10,-4,7,2,-5]返回：18解释：input数组有多个连续子数组，如[1,-2,3]，[3,10,-4,7,2]。在输入数组的所有子数组中，子数组的最大和为18，该数组为[3,10 展开全文

NumPy

发表于 2021-06-28 20:35:03

精华题解一、题目描述 JZ30 连续子数组的最大和题目大意：输入一个整型数组,数组里有正数也有负数.数组中的一个或连续多个整数组成一个子数组.求所有子数组的和的最大值.要求时间复杂度为 O(n).注意审题：要求时间复杂度为O(n) 二、算法1（前缀和）解题思路连续子数组问题可以联想到区间, 连续子数组展开全文

廿半

发表于 2019-12-26 13:52:01

典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可展开全文

牛客题解官

发表于 2020-06-01 14:40:58

#描述这是一篇针对初学者的题解，共用两种方法解决。知识点：数组，动态规划难度：一星 #题解题目抽象：给定一个数组，求连续子数组的最大和。 ##方法一：动态规划状态定义：dp[i]表示以i结尾的连续子数组的最大和。所以最终要求dp[n-1] 状态转移方程：dp[i] = max(array[ 展开全文

一叶浮尘

发表于 2019-08-17 20:52:18

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2} 展开全文

一颗闪闪发亮的马路星

发表于 2020-02-11 18:13:14

题目描述HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1, 展开全文

Khan201803011945114

发表于 2021-09-27 15:20:41

# -*- coding:utf-8 -*- class Solution: def FindGreatestSumOfSubArray(self, array): # write code here dp = [i for i in array] 展开全文

Oh~Sunny

发表于 2020-02-21 15:25:20

时间复杂度O(N)空间复杂度O(1) 动态规划: > dp[i] = dp[i-1] + p[i] # if i != 0 and dp[i-1] > 0 > dp[i] = p[i] # if i == 0 or dp[i-1] < 0代码: 展开全文

学无止境呀～

发表于 2019-09-06 19:59:31

30. 连续子数组的最大和题目描述HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6, 展开全文