我要招人

去企业版

首页 > 试题广场 >

连续子数组的最大和(二)

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

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

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。

1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个

3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组

4.返回的数组不计入空间复杂度计算

数据范围:

$1<=n<=10^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]

说明

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

示例2

输入

[1]

输出

[1]

示例3

输入

[1,2,-3,4,-1,1,-3,2]

输出

[1,2,-3,4,-1,1]

说明

经分析可知，最大子数组的和为4，有[4],[4,-1,1],[1,2,-3,4],[1,2,-3,4,-1,1]，故返回其中长度最长的[1,2,-3,4,-1,1]

示例4

输入

[-2,-1]

输出

[-1]

说明

子数组最小长度为1，故返回[-1]

算法知识视频讲解

牛客题解官

发表于 2022-04-25 18:51:00

精华题解题目的主要信息：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个不存在空数组返回的数组不计入空间复杂度计算举一反三：学习完本题的思路你展开全文

摸鱼学大师

发表于 2021-12-04 16:49:45

题目的主要信息：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个不存在空数组返回的数组不计入空间复杂度计算基本要求：时间复杂度：O(n)O 展开全文

每天学习一点

发表于 2021-12-10 22:19:35

相比较输出连续子数组最大和的数值情况，本题要求输出最大和对应的最长连续子数组。在动态规划的基础上，再增加四个变量：（1）保存当前遍历位置子串首尾位置；（2）最大和子串首尾位置。只需要根据实际情况判断是否要更新，如何更新，为了输出最长连续子数组，需要在当前子串值等于之前记录的最大子串值时也进行更新展开全文

Hzu_Lai

发表于 2022-03-03 09:48:32

动态规划求解思路及代码如下： public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param array int整型一维数组 * @return int整型一维数组 */ public 展开全文

姚OK

发表于 2022-03-25 16:47:30

代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 @param array int整型一维数组 @return int整型一维数组 class Solution: def FindGreatestSumOfSubArray(self , array: List[ 展开全文

passway

发表于 2022-01-23 10:53:31

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型一维数组 # class Solution: def FindGreatestSumOfSubArray(self , a 展开全文

zazaliu

发表于 2022-01-04 22:52:00

没看到typescript题解，我来补充一个，包含空间复杂度O(n),O(1)两种方法；题解：直接在连续数组最大和题解结果中改造，增加left，right变量记录子数组左右序号即可，那么问题就转化成了，如何更新left，right变量。 export function FindGreatest 展开全文

梦会绽放

发表于 2022-01-27 15:43:33

思路：滑动窗口。空间复杂度 O(1)（不包含用于结果返回的数组），遍历一遍数组，时间复杂度 O(n) 代码（Java实现） public class Solution { public int[] FindGreatestSumOfSubArray (int[] array) { 展开全文

designeer

发表于 2021-11-11 09:48:37

class Solution: def FindGreatestSumOfSubArray(self , array ): &nb 展开全文

像云一样的男纸

发表于 2021-12-16 15:34:44

# 用动态规划求一个连续数组最大和的时候，是一个dp数组，这个数组里面最大值才是最大和， # 那么问题是如何根据这个dp最长子数组呢？ # 方法如下： # 在求得dp的同时记录当前的dp的数组范围 # 如果当前dp是单个元素则要重置索引， #&nbs 展开全文

夜渡寒鸦呀

发表于 2022-05-17 16:35:49

C语言求解连续子数组的最大和（二）解题思路：由于已经使用动态规划解决了连续子数组的最大和（一）,那么思路相同，只不过这次的输出是要求输出这个连续子数组，那么可以添加一个变量，用于记录返回数组的末尾元素位置，同时还需要一个变量记录一下连续的数组长度。遇到的坑： 2.1 由于遇到多个最优解展开全文

问题信息

贪心动态规划数组双指针

上传者：牛客301499号

难度：

71条回答 463收藏 5136浏览

通过挑战的用户

查看代码

忙碌的华夫饼在提需求

2022-09-23 13:39:43
牛客74956...

2022-09-16 10:40:33
我就是不明白_

2022-09-16 09:54:47
牛客93777...

2022-09-15 23:04:59
TheDoge...

2022-09-15 22:25:53

连续子数组的最大和(二)

输入

输出

说明

输入

输出

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题