当前位置:网站首页>LeetCode:劍指 Offer 42. 連續子數組的最大和
LeetCode:劍指 Offer 42. 連續子數組的最大和
2022-07-06 08:45: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)
};
边栏推荐
猜你喜欢
Mobile phones and computers on the same LAN access each other, IIS settings
可变长参数
TP-LINK enterprise router PPTP configuration
Indentation of tabs and spaces when writing programs for sublime text
Unsupported operation exception
【嵌入式】Cortex M4F DSP库
Chrome浏览器的crash问题
Cisp-pte practice explanation
优秀的软件测试人员,都具备这些能力
游戏解包的危害及资源加密的重要性
随机推荐
JS native implementation shuttle box
China dihydrolaurenol market forecast and investment strategy report (2022 Edition)
Precise query of tree tree
704 二分查找
Double pointeur en langage C - - modèle classique
同一局域网的手机和电脑相互访问,IIS设置
电脑清理,删除的系统文件
LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置
[MySQL] lock
Chrome浏览器的crash问题
游戏解包的危害及资源加密的重要性
Sublime text in CONDA environment plt Show cannot pop up the problem of displaying pictures
可变长参数
C語言雙指針——經典題型
egg. JS getting started navigation: installation, use and learning
移位运算符
Browser thread
Modify the video name from the name mapping relationship in the table
pcd转ply后在meshlab无法打开,提示 Error details: Unespected eof
Revit 二次开发 HOF 方式调用transaction