「LeetCode」剑指Offer-42连续子数组的最大和⚡️

简介: 「LeetCode」剑指Offer-42连续子数组的最大和⚡️

image.png


前言🌧️



算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。

因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


当然,学习也是有侧重点的,作为前端我们不需要像后端开发一样对算法全盘掌握,有些比较偏、不实用的类型和解法,只要稍做了解即可。


题目🦀



剑指 Offer 42. 连续子数组的最大和


难度简单


输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。


要求时间复杂度为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 题相同:leetcode-cn.com/problems/ma…


解题思路🌵



  • 采用动态规划来求解
  • 将问题拆分为叠加的子问题
  • dp[i]=dp[i-1]+nums[i] 如果dp[i-1]<0 ; dp[i]=nums[i]


解法🔥



/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if(!nums){return 0}
    const start=nums[0]
    const dp=[start]
    let result=start
    for(let i=1;i<nums.length;i++){
        if(dp[i-1]>=0){
            dp[i]=dp[i-1]+nums[i]
        }else{
            dp[i]=nums[i]
        }
        result=Math.max(result,dp[i])
    }
    return result
};

时间复杂度:O(n)


空间复杂度:O(n)


结束语🌞


image.png


那么鱼鱼的LeetCode算法篇的剑指Offer-42连续子数组的最大和⚡️就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步

相关文章
|
6月前
|
人工智能 Java
每日一题《剑指offer》数组篇之连续子数组的最大和
每日一题《剑指offer》数组篇之连续子数组的最大和
52 0
每日一题《剑指offer》数组篇之连续子数组的最大和
【剑指offer】-连续子数组的最大和-30/67
【剑指offer】-连续子数组的最大和-30/67
|
算法
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
55 0
剑指offer 43. 连续子数组的最大和
剑指offer 43. 连续子数组的最大和
73 0
|
算法 C++ Python
每日算法系列【LeetCode 523】连续的子数组和
每日算法系列【LeetCode 523】连续的子数组和
|
索引
每日一题[LeetCode 689]三个无重叠子数组的最大和
闲来无事,为了保证日更,从今天开始每天更新一道LeetCode题解。 做题顺序是这样的:随机选择一题“困难”类型的题目。 因本人ACM退役颇久,代码多有疏漏,望多多见谅。
|
人工智能 算法 C++
每日算法系列【LeetCode 1031】两个非重叠子数组的最大和
每日算法系列【LeetCode 1031】两个非重叠子数组的最大和
代码随想录刷题|LeetCode 977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II
代码随想录刷题|LeetCode 977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II
Leetcode每日一题——三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k ,找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组,并返回这三个子数组。
78 0
|
算法 前端开发 程序员
「LeetCode」剑指Offer-44连续子数组的最大和⚡️
「LeetCode」剑指Offer-44连续子数组的最大和⚡️
106 0
「LeetCode」剑指Offer-44连续子数组的最大和⚡️