当前位置:网站首页>LeetCode:剑指 Offer 42. 连续子数组的最大和
LeetCode:剑指 Offer 42. 连续子数组的最大和
2022-07-06 08:44:00 【Bertil】
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为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
注意:本题与主站 53 题相同:https://leetcode-cn.com/problems/maximum-subarray/
解题思路
1.首先定义dp数组表示以当前元素做结尾的最大子序列和,然后遍历nums数组求每个dp元素值,最后返回最大值即可
2.状态转移方程:dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
代码
/** * @param {number[]} nums * @return {number} */
var maxSubArray = function(nums) {
let dp = [nums[0]]
for(let i = 1; i < nums.length; i ++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
}
return Math.max(...dp)
};
边栏推荐
- Browser thread
- 被破解毁掉的国产游戏之光
- After PCD is converted to ply, it cannot be opened in meshlab, prompting error details: ignored EOF
- Introduction to the differences between compiler options of GCC dynamic library FPIC and FPIC
- Problems in loading and saving pytorch trained models
- Marathon envs project environment configuration (strengthen learning and imitate reference actions)
- 【Nvidia开发板】常见问题集 (不定时更新)
- sublime text的编写程序时的Tab和空格缩进问题
- Unified ordering background interface product description Chinese garbled
- China Light conveyor belt in-depth research and investment strategy report (2022 Edition)
猜你喜欢
Beijing invitation media
Analysis of the source code of cocos2d-x for mobile game security (mobile game reverse and protection)
C language double pointer -- classic question type
UnsupportedOperationException异常
【ROS】usb_ Cam camera calibration
[MySQL] database stored procedure and storage function clearance tutorial (full version)
sublime text的编写程序时的Tab和空格缩进问题
[embedded] print log using JLINK RTT
深度剖析C语言数据在内存中的存储
【嵌入式】Cortex M4F DSP库
随机推荐
Trying to use is on a network resource that is unavailable
ROS compilation calls the third-party dynamic library (xxx.so)
软件压力测试常见流程有哪些?专业出具软件测试报告公司分享
China vanadium battery Market Research and future prospects report (2022 Edition)
Double pointeur en langage C - - modèle classique
Beijing invitation media
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
Excellent software testers have these abilities
JVM 快速入门
View computer devices in LAN
hutool优雅解析URL链接并获取参数
Unified ordering background interface product description Chinese garbled
gcc动态库fPIC和fpic编译选项差异介绍
Modify the video name from the name mapping relationship in the table
TP-LINK enterprise router PPTP configuration
Visual implementation and inspection of visdom
Navicat premium create MySQL create stored procedure
游戏解包的危害及资源加密的重要性
Marathon envs project environment configuration (strengthen learning and imitate reference actions)
[embedded] cortex m4f DSP Library