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

深藏阁楼爱情的钟 2022-10-26 04:57 115阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
    
    要求时间复杂度为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

#### 方案： ####

*  动态规划（贪心）

class Solution
    { 
    public:
        int maxSubArray(vector<int> &nums)
        { 
            int now = nums[0];
            int res = nums[0];
            int len = nums.size();
    
            for (int i = 1; i < len; i++)
            { 
                //清0
                if (now < 0)
                    now = 0;
                //记录当前值
                now += nums[i];
                //记录最大值
                res = res < now ? now : res;
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指 Offer 42. 连续子数组的最大和】

package com.example.demomain.demoleetcode.easy; / 输入一个整型数组，数组中的一个或连续多个

灰太狼/ 2023年09月26日 16:55/ 0 赞/ 17 阅读

相关【剑指Offer】42. 连续子数组的最大和

[NowCoder][] 题目描述 \{6, -3, -2, 7, -15, 1, 2, 2\}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。

小鱼儿/ 2022年11月29日 13:16/ 0 赞/ 91 阅读

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

题目输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1: > 输入: nums = \[-

我不是女神ヾ/ 2022年11月21日 11:33/ 0 赞/ 111 阅读

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

【题目】输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。【示例】输入: nums = \

「爱情、让人受尽委屈。」/ 2022年11月18日 01:29/ 0 赞/ 20 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

落日映苍穹つ/ 2022年10月29日 01:51/ 0 赞/ 114 阅读

相关剑指offer 42 连续子数组的最大和

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

深藏阁楼爱情的钟/ 2022年10月26日 04:57/ 0 赞/ 116 阅读

相关【leetcode】剑指 Offer 42. 连续子数组的最大和

剑指 Offer 42. 连续子数组的最大和题目难度：简单方法一：动态规划 > 链接：[https://leetcode-cn.com/problems

￡神魔★判官ぃ/ 2022年10月16日 01:58/ 0 赞/ 88 阅读

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

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1: 输入: nums = \[-2,1,-3,4

￡神魔★判官ぃ/ 2022年08月30日 00:45/ 0 赞/ 87 阅读

相关【剑指offer】面试题42：连续子数组的最大和

题目输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如，输入的数组为\{1

心已赠人/ 2022年06月11日 04:44/ 0 赞/ 117 阅读

相关【剑指offer】面试题42：连续子数组的最大和

> 题目：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。牛客网链接：[https:/

秒速五厘米/ 2022年04月22日 15:16/ 0 赞/ 134 阅读