精选50题之 53. 最大子序和

ゝ一世哀愁。 2024-04-18 19:12 42阅读 0赞

### 腾讯精选练习（50 题）之 53. 最大子序和 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式

## 原题目链接 ##

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

> 示例:  
> 输入: \[-2,1,-3,4,-1,2,1,-5,4\],  
> 输出: 6  
> 解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

进阶:  
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

## 题目分析 ##

这是动态规划法的中的经典问题。  
直观来说：

*  当前i个数之和大于0时，新结果为前（i+1）个数之和；
 *  当前i个数之和小于等于0时，新结果仅为第（i+1）个数。

## 解题分析 ##

有多种实现，只要是语句的不同

*  ? : 三重运算符
 *  if( > 0) 判断比较
 *  max() 直接比较

## 代码实现 ##

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            int res = INT_MIN;
            int past = 0;
            for(int i = 0; i < nums.size(); i++)
            {
        
                int cur = max(past, 0) + nums[i];
                res = max(res, cur);
                past = cur;
            }
            return res;
        }
    };

![在这里插入图片描述][20190910221653477.png]  
复杂度分析

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

## 其他方式 ##

除了动态规划外，亦可以用分治法解决。  
因为最大子序和所在位置，无非三种情况：

*  数组前部
 *  数组中部
 *  数组尾部

但由于需要对数组递归遍历，代码实现较动态规划更复杂，且效率更低

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

所以就不写了?

[20190910221653477.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/baec3d0ee427447490ebae4640b67569.png

发表评论取消回复

表情：

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

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

相关阅读

相关 53：最大子序和

法1：暴力法，但是提交时会超时，O（n^2) class Solution: def maxSubArray(self, nums: List[...

约定不等于承诺〃/ 2024年04月18日 22:34/ 0 赞/ 74 阅读

相关精选50题之 53. 最大子序和

腾讯精选练习（50 题）之 53. 最大子序和 * * 原题目链接 * 题目分析 * 解题分析 * 代码实现 *...

ゝ一世哀愁。/ 2024年04月18日 19:12/ 0 赞/ 43 阅读

相关 LeetCode题目之腾讯精选练习（50题）：最大子序和

题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 **示例**: 输入: [-2,1,-3,4...

小咪咪/ 2024年04月17日 20:48/ 0 赞/ 74 阅读

相关【腾讯精选练习 50 题】11—最大子序和【简单】

题目链接 [53. 最大子序和【简单】][53.] 题目简介给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最

素颜马尾好姑娘i/ 2022年11月16日 01:30/ 0 赞/ 217 阅读

相关 53. 最大子序和

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

短命女/ 2022年10月22日 08:00/ 0 赞/ 203 阅读

相关 53. 最大子序和

> 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > > > > 示例 1： > > 输入：nums = \

ゝ一世哀愁。/ 2022年10月05日 12:53/ 0 赞/ 190 阅读

相关 leetcode 53 最大子序和

前言题目：[53. 最大子序和][53.] 参考题解：[最大子序和-代码随想录][-] -------------------- 提交代码 (残酷)思路：前

女爷i/ 2022年09月14日 09:49/ 0 赞/ 201 阅读

相关 53.最大子序和

题目描述：给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例：输入：nums = [-2,1,-

怼烎@/ 2022年08月28日 12:52/ 0 赞/ 174 阅读

相关 53. 最大子序和

[53. 最大子序和][53.] 题目描述给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

缺乏、安全感/ 2021年11月02日 00:08/ 0 赞/ 304 阅读

相关 LeetCode53. 最大子序和

题目描述给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,

╰+攻爆jí腚メ/ 2021年10月19日 08:46/ 0 赞/ 330 阅读