算法：连续子数组的最大和

深藏阁楼爱情的钟 2024-04-01 10:26 61阅读 0赞

![e9333cf73665af603403d93d5e00ea9f.jpeg][]

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

## 示例 ##

*  输入: nums = \[-2,1,-3,4,-1,2,1,-5,4\]
 *  输出: 6
 *  解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

## 提示 ##

*  1 <= arr.length <= 10^5
 *  \-100 <= arr\[i\] <= 100

## 方法：动态规划 ##

*  状态定义：dp\[i\] 表示以 nums\[i\] 结尾的连续子数组的最大和；
 *  状态转移方程：
    
     *  如果 dp\[i - 1\] > 0， dp\[i\] = dp\[i - 1\] + nums\[i\];
    
     *  如果 dp\[i - 1\] ≤ 0，dp\[i\] = nums\[i\]。
 *  初始化：dp\[0\] = nums\[0\];
 *  输出：max(dp);

**代码如下：**

![bcea6c5e172514a4c311926982994f97.jpeg][]

## 复杂度分析 ##

*  时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
 *  空间复杂度：O(1)。我们只需要在常数空间存放若干变量。

## END ##

勤能补拙是良训，一分耕耘一分才，赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。

![3e46db98431a4750ac8694ebba693e16.png][]

[e9333cf73665af603403d93d5e00ea9f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f540a099f2604b98b56c0d3ab205b996.jpeg
[bcea6c5e172514a4c311926982994f97.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f11c78809ed348b08fb4c46e81be982e.jpeg
[3e46db98431a4750ac8694ebba693e16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e0a941959b6d471e9b1d0714c36b5362.png

发表评论取消回复

表情：

评论列表（有 0 条评论，61人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：连续子数组的最大和

![e9333cf73665af603403d93d5e00ea9f.jpeg][] 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

深藏阁楼爱情的钟/ 2024年04月01日 10:26/ 0 赞/ 62 阅读

相关连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。

短命女/ 2022年09月25日 12:19/ 0 赞/ 227 阅读

相关最大连续子数组和

最大连续子数组和 1. 题目描述输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有

快来打我*/ 2022年08月06日 01:06/ 0 赞/ 211 阅读

相关连续子数组的最大和

虽然在剑指offer上看到过，在真正做这道题的时候才发现自己的不足在线判题传送门： [点这里][Link 1] 题目：一个数组有 N 个元素，求连续子数组的

￡神魔★判官ぃ/ 2022年06月09日 03:37/ 0 赞/ 197 阅读

相关连续子数组的最大和

![这里写图片描述][70] 一、分析使用动态规划 F（i）：以array\[i\]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变 F（i）=ma

喜欢ヅ旅行/ 2022年05月25日 07:20/ 0 赞/ 215 阅读

相关连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

小灰灰/ 2022年05月14日 09:14/ 0 赞/ 227 阅读

相关连续子数组的最大和 java

连续子数组的最大和 java 题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子

分手后的思念是犯贱/ 2022年05月12日 13:40/ 0 赞/ 202 阅读

相关连续子数组的最大和

[连续子数组的最大和][Link 1] 题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需

古城微笑少年丶/ 2022年03月25日 15:37/ 0 赞/ 250 阅读

相关连续子数组的最大和

时间限制：1秒空间限制：32768K 热度指数：197703 本题知识点：数组算法知识视频讲解题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同

Myth丶恋晨/ 2022年03月09日 10:49/ 0 赞/ 229 阅读

相关连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候

ゞ浴缸里的玫瑰/ 2021年09月30日 02:00/ 0 赞/ 318 阅读