当前位置:网站首页>Leetcode: Sword finger offer 42 Maximum sum of continuous subarrays
Leetcode: Sword finger offer 42 Maximum sum of continuous subarrays
2022-07-06 08:45:00 【Bertil】
Enter an integer array , One or more consecutive integers in an array form a subarray . Find the maximum sum of all subarrays .
The required time complexity is O(n).
Example 1:
Input : nums = [-2,1,-3,4,-1,2,1,-5,4]
Output : 6
explain : Continuous subarray [4,-1,2,1] And the biggest , by 6.
Tips :
- 1 <= arr.length <= 10^5
- -100 <= arr[i] <= 100
Be careful : This topic and the main station 53 The question is the same :https://leetcode-cn.com/problems/maximum-subarray/
Their thinking
1. First define dp Array represents the largest subsequence ending with the current element and , Then traverse nums Array for each dp Element value , Finally, return the maximum value
2. State transition equation :dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
Code
/** * @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)
};
边栏推荐
- Variable length parameter
- C语言双指针——经典题型
- Sublime text using ctrl+b to run another program without closing other runs
- poi追加写EXCEL文件
- 如何进行接口测试测?有哪些注意事项?保姆级解读
- Unsupported operation exception
- 目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- LeetCode:26. 删除有序数组中的重复项
- Research Report on supply and demand and development prospects of China's high purity aluminum market (2022 Edition)
猜你喜欢
Restful API design specification
生成器参数传入参数
egg. JS getting started navigation: installation, use and learning
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
704 binary search
JS native implementation shuttle box
【嵌入式】Cortex M4F DSP库
win10系统中的截图,win+prtSc保存位置
JVM performance tuning and practical basic theory - Part 1
Light of domestic games destroyed by cracking
随机推荐
[NVIDIA development board] FAQ (updated from time to time)
LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置
Marathon envs project environment configuration (strengthen learning and imitate reference actions)
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
R language uses the principal function of psych package to perform principal component analysis on the specified data set. PCA performs data dimensionality reduction (input as correlation matrix), cus
ROS compilation calls the third-party dynamic library (xxx.so)
Analysis of the source code of cocos2d-x for mobile game security (mobile game reverse and protection)
C language double pointer -- classic question type
Current situation and trend of character animation
Warning in install. packages : package ‘RGtk2’ is not available for this version of R
Navicat Premium 创建MySql 创建存储过程
如何进行接口测试测?有哪些注意事项?保姆级解读
Sublime text using ctrl+b to run another program without closing other runs
Variable length parameter
Process of obtaining the electronic version of academic qualifications of xuexin.com
R language ggplot2 visualization: place the title of the visualization image in the upper left corner of the image (customize Title position in top left of ggplot2 graph)
TCP/IP协议
After PCD is converted to ply, it cannot be opened in meshlab, prompting error details: ignored EOF
[MySQL] lock
LeetCode:剑指 Offer 03. 数组中重复的数字