letecode [53] - Maximum Subarray

亦凉 2021-11-04 11:06 248阅读 0赞

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
    Output: 6
    Explanation: [4,-1,2,1] has the largest sum = 6.

**题目大意：**

给定数组，找到具有最大和的连续子数组，返回该最大和。

**理  解：**

初始最大和max、临时数值sum和为nums\[0\]。

当sum<0 时，若下一个数nums\[i\] 大于sum，则sum重新设置为nums\[i\]。

当sum>0时，直接加上下一个数nums\[i\]。

每次都需将sum与最大和max比较，更新max值。

**代 码 C++：**

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int n = nums.size();
            if(n==0) return 0;
            int max = nums[0],sum=nums[0] ,i;
            for(i=1;i<n;++i){
         
    　　　　　　　 
                if(sum<0 && sum<nums[i]){
                    sum = nums[i];
                    if(max<sum) max = sum;
                    continue;
                }
                sum = sum + nums[i];
                if(max<sum) max = sum;
            }
            if(max<sum) max = sum;
            return max;
        }
    };

**运行结果：**

执行用时 : 12  ms　　内存消耗 :  9.4 MB

转载于:https://www.cnblogs.com/lpomeloz/p/10972182.html

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 53. Maximum Subarray (动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

深碍√TFBOYSˉ_/ 2024年04月17日 23:16/ 0 赞/ 83 阅读

相关 LeetCode - Easy - 53. Maximum Subarray

Topic Array, Divede and Conquer, Dynamic Programming Description [https://leetcod

今天药忘吃喽~/ 2022年12月27日 09:05/ 0 赞/ 474 阅读

相关 LeetCode53——Maximum Subarray

LeetCode53——Maximum Subarray 题意：就是经典的动态规划问题。这里直接给出公式： dp\[i\]表示以nums\[i\]结尾的最大子序列和

梦里梦外;/ 2022年08月09日 12:56/ 0 赞/ 149 阅读

相关 LeetCode 53/152 Maximum Subarray/Maximum Product Subarray---DP **

一：[Maximum Subarray][] 题目： Find the contiguous subarray within an array (containing at

╰+哭是因爲堅強的太久メ/ 2022年08月07日 12:43/ 0 赞/ 18 阅读

相关 leetcode 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has

比眉伴天荒/ 2022年07月28日 01:05/ 0 赞/ 182 阅读

相关【LeetCode】53. Maximum Subarray

53. Maximum Subarray Find the contiguous subarray within an array (containing at lea

布满荆棘的人生/ 2022年07月26日 05:14/ 0 赞/ 196 阅读

相关 [leetcode]: 53. Maximum Subarray

1.题目 Find the contiguous subarray within an array (containing at least one number) wh

Bertha 。/ 2022年06月15日 02:37/ 0 赞/ 181 阅读

相关 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which

浅浅的花香味﹌/ 2022年06月02日 12:19/ 0 赞/ 193 阅读

相关 53. Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one num

我会带着你远行/ 2022年04月21日 23:46/ 0 赞/ 199 阅读

相关 letecode [53] - Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one num

亦凉/ 2021年11月04日 11:06/ 0 赞/ 249 阅读