当前位置:网站首页>2022.08.06_每日一题
2022.08.06_每日一题
2022-08-09 18:00:00 【诺.い】
53. 最大子数组和
题目描述
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。
coding
用 pre 记录局部最优值,用 max 记录全局最优值。
每遍历一个新元素时,判断(已遍历的连续子数组的和)加上(当前元素值),与(当前元素值)对比谁更大。
(1)如果已遍历的连续子数组的和 + 当前元素值 >= 当前元素值
说明(已遍历的连续子数组的和)是大于等于0的,令 pre= 已遍历的连续子数组的和 + 当前元素值。
(2)如果已遍历的连续子数组的和 + 当前元素值 < 当前元素值
说明(已遍历的连续子数组的和)是小于0的,加上这部分只会使子数组和变得更小,故可直接抛弃掉这部分,令 pre = 当前元素值。
(3)对比 pre 和 max,如果 pre 更大,则更新到 max 中。
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int max = nums[0];
for (int i = 0; i < nums.length; i ++) {
pre = Math.max(pre + nums[i], nums[i]);
max = Math.max(pre, max);
}
return max;
}
}
边栏推荐
- Go-Excelize API源码阅读(五)—— Close()
- How to stop the test after reaching a given number of errors during stress testing in JMeter
- ceph集群部署
- grafana docks local ldap
- anno arm移植Qt环境后,编译正常,程序无法正常启动问题的记录
- mysql如何查看所有复合主键的表名?
- 程序健壮性
- 字节二面:可重复读隔离级别下,这个场景会发生什么?
- Detailed explanation of VIT transformer
- LeetCode笔记:Biweekly Contest 84
猜你喜欢
What is the Treasure Project (TPC), a dark horse with wings in 2022!
IMX6ULL—汇编LED灯
软件设计的七大原则
读大学有用吗?
艺术与科技的狂欢,云端XR支撑阿那亚2022砂之盒沉浸艺术季
golang单元测试:testing包的基本使用
How to play with container local storage through open-local? | Dragon Lizard Technology
Flink on Yarn
使用mysql:5.6和 owncloud 镜像,构建一个个人网盘
[免费专栏] Android安全之GDB动态调试APP
随机推荐
Win10系统80端口被占用的解决方法
100+开箱即用的AI工具箱;程序员150岁长寿指南;『地理空间数据科学』课程资料;Graphic数据可视化图表库;前沿论文 | ShowMeAI资讯日报
三面(技术 +HR 面试)网易,分享我的面试经验!(已拿 offer)
数据库注入提权总结(一)
uniapp 实现底部导航栏tabbar
字节二面,差点倒在了MySQL上面
重庆智博会|2022智博会到底有哪些看点?拭目以待
[免费专栏] Android安全之ZIP文件目录遍历漏洞
anno arm移植Qt环境后,编译正常,程序无法正常启动问题的记录
LeetCode做题小结
shell脚本基础语句使用(一)
C程序设计-第四版
与同步传递相关的获取-释放序列
Pytorch 固定部分参数训练
URLError: <urlopen error [Errno 11004] getaddrinfo failed>调用seaborn-data无法使用
ARM Assembly Basics
loadrunner脚本--参数化
[免费专栏] Android安全之安卓APK浅析
基于AWS构建云上数仓第一步:云平台的基础概念
mysql双主备份失败?