最大累加数组问题（最大子序和问题）

我不是女神ヾ 2022-12-24 10:54 161阅读 0赞

## 题目描述 ##

给定一个数组arr，返回子数组的最大累加和  
例如，arr = \[1, -2, 3, 5, -2, 6, -1\]，所有子数组中，\[3, 5, -2, 6\]可以累加出最大的和12，所以返回12.  
\[要求\]  
时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

## 示范 ##

[1, -2, 3, 5, -2, 6, -1]
    12
    
    3+5+（-2）+6=12

## 思路分析 ##

这是一个很有意思的问题，如果我们用暴力法，逐个相加对前一个和进行比较这是一个很繁琐的问题，但是我们可以使用分治法，提高效率，遍历这个数组将遍历得到的元素进行相加，如果这个和大于0继续相加，如果小于0将sum置为0,继续相加，直到找到maxsum

# python实现 #

class Solution:
        def maxsumofSubarray(self , arr ):
            # write code here
            if len(arr) == 0:
                return 0
            maxsum,nowsum=0,0
            for i in arr:
                nowsum+=i
                if nowsum>maxsum:
                    maxsum=nowsum
                elif nowsum<0:
                    nowsum=0
            return maxsum

C语言实现

int maxsumofSubarray(int* arr, int arrLen ) {
        
        // write code here
        int nowsum=0;
        int maxsum=0;
        int i=0;
        for(i=0;i<=arrLen-1;i++)
            nowsum=nowsum+arr[i];
            if(nowsum>maxsum)
                maxsum=nowsum;
            else if(nowsum<0)
                nowsum=0;
        return maxsum;
    }

![在这里插入图片描述][20201127200147896.png]

[20201127200147896.png]: /images/20221120/7a3d6b4570604ec596223226b1edb4e3.png

发表评论取消回复

表情：

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

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

相关阅读

相关牛客子矩阵最大累加和问题

题目链接：[https://www.nowcoder.com/practice/cb82a97dcd0d48a7b1f4ee917e2c0409?tpId=101&tqId=3

喜欢ヅ旅行/ 2023年06月04日 14:57/ 0 赞/ 18 阅读

相关最大累加数组问题（最大子序和问题）

题目描述给定一个数组arr，返回子数组的最大累加和例如，arr = \[1, -2, 3, 5, -2, 6, -1\]，所有子数组中，\[3, 5, -2, 6

我不是女神ヾ/ 2022年12月24日 10:54/ 0 赞/ 162 阅读

相关最大子序和

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

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

相关连续子数组最大和问题

1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x ![132021534183635.png][] 应该返回 x\[2..6\]的和1

冷不防/ 2022年07月18日 01:12/ 0 赞/ 225 阅读

相关最大子数组问题

最大子数组问题从一个数组中寻找一个子数组（最少一个元素），使子数组中元素之和最大（必定包含负数，不然最大子数组就是原数组本身）。暴力求解我们很容易的想到一个

曾经终败给现在/ 2022年06月07日 10:17/ 0 赞/ 199 阅读

相关子数组的最大累加和问题

![Center][] //子数组的最大累加和问题 public class subArrAdd{ //获得子数组的最大累加和

比眉伴天荒/ 2022年05月28日 22:48/ 0 赞/ 188 阅读

相关最大子序和

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

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

相关最大子序和

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

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

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

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

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

相关最大子序和

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

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