剑指 Offer 42. 连续子数组的最大和
2024-09-07 19:17:23
题目描述
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为\(O(n)\)。
示例1:
输入: 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
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
代码实现
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> max_sum;
max_sum.push_back(nums[0]);
for (unsigned int i = 1; i < nums.size(); i++)
max_sum.push_back((max_sum[i - 1] > 0) ? (max_sum[i - 1] + nums[i] : nums[i]);
int max = -101;
for (unsigned int i = 0; i < max_sum.size(); i++)
max = (max > max_sum[i]) ? max : max_sum[i];
return max;
}
};
思路解析
max_sum[i]
以nums[i]
为结尾的连续子数组最大和。max_sum[0] = nums[0]
max_sum[i] = (max_sum[i - 1] > 0) ? (max_sum[i - 1] + nums[i] : nums[i]
时间复杂度\(O(n)\),空间复杂度\(O(n)\)。
最新文章
- The first DP!
- CheckBox设置Enabled为False后,无法修改ForeColor
- nyoj 170 网络的可靠性
- android 修改系统的dialog样式
- UVa 1625 Color Length
- poj 4618 暴力
- openMPI小集群安装
- ELK 之二:ElasticSearch 和Logstash高级使用
- Java中处理二进制移位
- win10- *.msi 软件的安装,比如 SVN安装报2503,2502
- dedecms在php7下的使用方法,织梦dedecsm后台一片空白的解决方法
- MFC中自定义消息
- 【Python】 docker-py 用Python调用Docker接口
- ArcGis Python脚本——遍历输出面或折线要素的折点坐标
- django 单点登录思路-装饰器
- Python对象相关内置函数
- ES6 必须要用的数组Filter() 方法,不要再自己循环遍历了!!!
- springboot配置Druid监控
- MapServer Tutorial——MapServer7.2.1教程学习——第一节用例实践:Example1.1 A map with single layer
- 推荐一个实用的 .gitignore 文件
热门文章
- JS click延迟解决方案
- Vulnhub靶场-Me and my girlfriend 学习笔记
- ASP.NET Core - 实现Http自定义请求头策略
- C#LeetCode刷题之#643-子数组最大平均数 I( Maximum Average Subarray I)
- golang的fmt
- NumPy速查笔记(持续更新中)
- PYTHON替代MATLAB在线性代数学习中的应用(使用Python辅助MIT 18.06 Linear Algebra学习)
- 剑指offer数组中重复的数字
- java中Math的常用方法整理
- hdfs-default.xml