11-05 最大子序和

曾经终败给现在 2022-12-19 06:23 81阅读 0赞

[原题：][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70_pic_center]  
**解法：**  
首先是最大值的定义。INT\_MIN这个是默认的，INT\_MAX整形的最大值；  
利用**贪心的思想**求解这道题，其时间复杂度会控制在O(N)。\*\*所谓贪心，就是只管当前能够得到的最大值，别的事情都不管。\*\*因为求的是最大连续子列和，那么当前几个数字相加得到的结果比初始最大值要大的时候，那么就更新，如果前面的数字小于零，那么直接讲求得的和重置为0，重新开始即可。

有很多人提到了动态规划或者暴力的解法，可能容易想到但不容易操作，如果限定了时间，暴力在数据规模很大的时候会超时。

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

[Link 1]: https://leetcode-cn.com/problems/maximum-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTg4NTIzMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8787311e6e7e4f4d91b93cc747a1e97a.png

发表评论取消回复

表情：

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

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

相关阅读

相关最大子序和

最大子序和 1、参考资料 https://leetcode-cn.com/problems/maximum-subarray/ 2、题目要求 > 题目描述

古城微笑少年丶/ 2022年12月05日 10:13/ 0 赞/ 206 阅读

相关 53. 最大子序和

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

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

相关 53.最大子序和

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

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

相关最大子序和

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

妖狐艹你老母/ 2022年04月16日 02:12/ 0 赞/ 230 阅读

相关最大子序和

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

灰太狼/ 2022年02月26日 04:52/ 0 赞/ 257 阅读

相关最大子序和——最大子矩阵

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

清疚/ 2022年02月20日 05:52/ 0 赞/ 352 阅读

相关最大子序和

1.暴力解法 O(n^3) class Solution { public: int FindGreatestSumOfSubArray(v

快来打我*/ 2022年02月05日 12:51/ 0 赞/ 261 阅读

相关最大子序和

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

川长思鸟来/ 2022年01月20日 04:09/ 0 赞/ 275 阅读

相关 53. 最大子序和

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

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

相关 LeetCode：最大子序和

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

水深无声/ 2021年11月01日 03:08/ 0 赞/ 366 阅读