我要招人

去企业版

首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题

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

给定一个长度为 n 的数组 arr ，返回其中任意连续子数组的最大累加和

题目保证没有全为负数的数据

数据范围： $1 \le n \le 100000$ ，数组中元素值 $|val| \le 100$

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

示例1

输入

[1, -2, 3, 5, -2, 6, -1]

输出

说明

[3,6]范围内的子数组之和最大，3+5-2+6=12

示例2

输入

[1]

输出

备注:

算法知识视频讲解

冬夜多漫长

发表于 2021-03-20 14:35:40

精华题解该题的本质是一个个往后累加，若过程中累加和小于0，那么就需要将前面的数都舍掉，继续重新从下一个数累加，过程中需要保存累加的最大值，若加上后一个数大于前面的值，则对最大值重新赋值，反之则不变。

堆栈哲学

发表于 2021-07-09 17:37:06

精华题解题意分析理解什么是子数组？要求子数组最大累加和注意题目对时间复杂度和空间复杂度的要求时间：O（N）空间：O（1）注意备注信息：包含了所给数据的边界范围，这对算法的选择至关重要的。解法一：暴力解思路步骤：常规思路，直接两层for循环暴力枚举找到符合题意的最大累加和虽然理展开全文

漫漫云天自翱翔

发表于 2021-07-12 09:27:23

精华题解题解一：动态规划题解思路：使用dp数组表示子问题累加和， ans表示当前数组累加和最大值图示：复杂度分析：时间复杂度：O(N) 空间复杂度：O(N)实现如下： class Solution { p 展开全文

Antrn

发表于 2020-10-08 11:48:58

看了前面的解答，都有问题，自测调试用示例1的输入输出都通过不了。我的想法是：总的来说，解题思路就是从前往后推，要保证每个位置的值都起码比原本的大。注意每次都要用m保存当前时刻的最大累积和，最后直接返回就ok。 class Solution { public: int maxsumofSuba 展开全文

有理想的咕咕

发表于 2020-12-16 10:37:09

遇到这种动态公式非常明显的题，直接考虑动态规划，并且列出转移方程设置动态数组dp[i]：下标为i处之前的最大累加和(可能不包括自己也可能包括自己)以下为转移方程初始化dp[0] = arr[0] dp[i-1] > 0 -> dp[i] = dp[i-1] + arr[i] dp 展开全文

Maokt

发表于 2020-11-18 13:05:11

思路:第一个元素不为负数，如果前面数的累加值加上当前数后的值比当前数小，说明当前数对整体和是有害的；反之，说明当前数对整体和是有利的。遍历数组元素，如果前面的累加值为负数或者0，则对累加值清0重新计算，把当前的第i个元素赋值给累加值，反之，将之前的累加值加上当前的第i个元素值 class Solu 展开全文

小洋芋热爱NLP

发表于 2021-01-11 10:51:31

- 1、题目描述： - 2、题目链接： https://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd?tpId=117&&tqId=35068-3、设计思想：详细操作流程看下图： -4、视频讲解链接B站视频讲展开全文

THE_LIN

发表于 2020-09-11 21:55:25

由于题目对空间复杂度有要求，O(1),所以直接在arr容器进行分治操作。思路：从容器第二个元素开始遍历，判断当前数与前一个数之和与当前数之间哪个较大，把大的数赋值给当前位置，遍历一遍之后最大累计和就在容器末尾，以此分而治之，分治法解该题非常合适。代码：class Solution {public: 展开全文

LaN666

发表于 2021-03-07 16:33:43

分治动态规划其实题目可以用动态规划做，很简单的动态规划题目，而且也是最优解先看代码: public int maxsumofSubarray (int[] arr) { int n = arr.length; if(n == 1) retu 展开全文

倔强青铜从不倔强🇨🇳

发表于 2020-10-07 13:53:26

本题目要求时间复杂度为O(n)，一开始我也是有点懵逼的，看了下题解，发现很多不符合题目标准，本题的测试数据也无法覆盖全面，有些解答有些问题。故自己写了一下详细的解题思路。1.首先我觉得这道题跟分治法没有什么关系。2.原理就是从一端推数据，可以从index=1开始推进判断，如果"前一个值" + "当前展开全文