首页 > 试题广场 >

连续子数组的最大和

[编程题]连续子数组的最大和

热度指数：650186 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

$1 <= n <= 2\times10^5$

$-100 <= a[i] <= 100$

要求:时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$

进阶:时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$

示例1

输入

[1,-2,3,10,-4,7,2,-5]

输出

说明

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入

[2]

输出

示例3

输入

[-10]

输出

-10

算法知识视频讲解

推荐

信念哥

public class Solution {
     public int FindGreatestSumOfSubArray(int[] array) {
         if (array.length==0 || array==null) {
             return 0;
         }
         int curSum=0;
         int greatestSum=0x80000000;
         for (int i = 0; i < array.length; i++) {
             if (curSum<=0) {
                 curSum=array[i]; //记录当前最大值
             }else {
                 curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。
             }
             if (curSum>greatestSum) {
                 greatestSum=curSum; 
             }
         }
         return greatestSum;
     }
 }

编辑于 2015-07-26 20:51:19 回复(100)

Python

菜鸡尼欧

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        ret = array[0]
        for i in range(1, len(array)):
            array[i] += array[i - 1] if array[i - 1] > 0 else 0
            ret = max(ret, array[i])
        return ret

发表于 2022-02-19 20:33:03 回复(0)

Python

牛客930331173号

首先注意题目是要求“连续”，既索引必须是0，1，2，3/3，4，5这样的，不能是2，3，5之类的。

所以由此可以使用dp解决。

设dp[i]为以下标i元素结尾的最大和

递推式：dp[i]=max(x_i+dp[i-1],x_i)

初始状态 dp[0]=array[0]

思路就是：如果该元素之前的最大和加上当前元素值小于当前元素，那就从当前元素重新开始计算，否则按两者加和作为此处的最大和。

最后得到的dp数组中最大的那一个，就是答案。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self,a):
        # write code here
        
        dp = [0]*len(a)
        dp[0]=a[0]
    
        for i in range(1,len(a)):
            if (dp[i-1]+a[i])<a[i]:
                dp[i]=a[i]

            else:
                dp[i]=dp[i-1]+a[i]
        return max(dp)

编辑于 2021-05-02 17:24:30 回复(0)

Python

牛客541273514号

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return None
        n=len(array)
        res=[]
        for i in range(1,n+1):
            res.append(self.sumOfsubArray(array, i))
        return max(res)
            
    def sumOfsubArray(self,array,k):
        if not array:
            return None
        n=len(array)
        res=[]
        for i in range(0,n-k+1):
            res.append(sum(array[i:i+k]))
        return max(res)

发表于 2021-04-21 16:24:33 回复(0)

Python

炸鱼薯条

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0
        dp = array[:]
        for i in range(1, len(dp)):
            if dp[i - 1] > 0:
                dp[i] += dp[i - 1]
        return max(dp)

发表于 2021-03-20 10:07:16 回复(0)

Python

牛客578317901号

# -*- coding:utf-8 -*-
class Solution:
    # 注意这里的首个数字不一定从0个开始
    def FindGreatestSumOfSubArray(self, array):
        if len(array) < 1:
            return []
        elif len(array) == 1:
            return array[0]
        else:
            ret = []
            i = 0
            n = len(array)
            while i < n: # i在增加，况且array每次弹出一个元素len(array)依旧是原始值,这里不可以递减
                lst = [] # lst列表在每次开始循环的时候清空
                for tmp in array:
                    lst.append(tmp)
                    ret.append(sum(lst)) # 要把所有可能的sum结果加入ret，ret要在循环之外
                array.pop(0) # 不一定从首位开始，所以更换起始值
                i += 1
            return max(ret)
            # 要么i增加，array不变，要么array减少，len不变

发表于 2020-09-09 16:05:46 回复(0)

Python

火树银花zjl

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        length=len(array)
        if length==0:
            return 0
        else:
            a=array[0]
            b=array[0]
            for i in range(1,length):
                if a<=0:
                    a=array[i]
                else:
                    a+=array[i]
                if a>b:
                    b=a
            return b

发表于 2020-08-27 22:59:37 回复(0)

Python

sk8_wt

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        length = len(array)
        if length == 1:
            return sum(array)
        l2 = []
        array.append(0)
        for i in range(length):
            l1 = []
            for j in range(i+1,length+1):
                l1.append(sum(array[i:j]))
            l2.append(max(l1))
        return max(l2)

发表于 2020-08-13 22:20:27 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        res = max(array)
        tmp = 0
        for i in array:
            tmp = max(i,tmp+i)
            res = max(tmp,res)
        return res

注意：tmp = max(i,tmp+i)为什么不是max(tmp,tmp+i)，是因为如果tmp在进入此次循环之前，已经和res比较过了，所以如果上一轮的tmp大，也会通过res保存下来，不用担心丢失的问题。

发表于 2020-07-24 21:10:03 回复(0)

Python

liucr.baozi

1.子问题拆分： $dp[i]$ 表示第 $i$ 个字符结尾的的最大子序和，状态 $dp[i]$ 有三种情况： $dp[i-1]$ 个和加上 $nums[i]$ ， $nums[i]+nums[i-1]$ ， $nums[i]$ 中的最大值，其值为 $dp[i]=max\{dp[i-1]+nums[i],nums[i]+nums[i-1],num[i]\}$
2.其实就是针对前 $i$ 个的最大和选择和不选择的问题，在位置 $i$ 处三种选择，加上前 $i-1$ 项的最大和，从 $i-1$ 开始从新加，从 $i$ 开始从新算

def maxSubArray(nums):
    if not nums:
        return 0
    dp = [0]*len(nums)
    dp[0] = nums[0]
    for i in range(1,len(nums)):
        tmp_sum = 0
        tmp_sum = max(dp[i-1]+nums[i],nums[i]+nums[i-1],nums[i])
        dp[i] = tmp_sum
    return max(dp)

发表于 2020-07-21 19:13:58 回复(0)

Python

一直爬的蜗牛

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        dp = [i for i in array]
        for i in range(1, len(array)):
            dp[i] = max(dp[i-1]+array[i], array[i])
        return max(dp)
    
    #为何牛逼的想法总是别人想出来的！！！

发表于 2020-06-21 22:46:17 回复(0)

Python

Chloe_y

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        result=[]
        i = 0
        while i < len(array):
            list = []
            list = array[i:len(array)]
            result.append(self.maxnum(list))
            i = i+1
        r = max(result)
        return r
    
    def maxnum(self,list):
        result = []
        sum = 0
        for i in range(len(list)):
            sum = sum + list[i]
            result.append(sum)
        r = max(result)
        return r

发表于 2020-05-30 18:21:08 回复(0)

Python

牛客473055830号

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        n = len(array)
        max1 = array[0]
        for i in range(n):
            result = array[i]
            if max1 < result:
                    max1 = result
            for j in range(i + 1, n):
                result += array[j]
                if max1 < result:
                    max1 = result
                if result <= 0:
                    break
        return max1

发表于 2020-05-27 23:59:04 回复(0)

Python

Kuriyamaaa

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        a=array
        lena=len(a)
        if lena==0:
            return 0
        if lena==1:
            return max(a)
        temp=[]
        temp.append(max(a))
        for i in range(lena-1):
            for j in range(i+1,lena):
                if a[j]>0:
                    temp.append(sum(a[i:j+1]))
        return max(temp)
        # write code here

发表于 2020-05-27 15:51:12 回复(0)

Python

zzgforever

思路：确立累加数组的最大和最大的子数组和，始终保持最大值

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        l =  len(array)
        if not array:
            return None
        cursum = 0
        maxsum = array[0]
        
        for i in range(0,l):
            if cursum <= 0:
                cursum = array[i]
            else:
                cursum += array[i]
            maxsum = max(cursum,maxsum)
        return maxsum

编辑于 2020-05-04 11:12:35 回复(0)

Python

未央的央

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        a=[]
        b=0
        for i in array:
            a.append(i)
            if sum(a)<0:
                a=[]
            else:
                if sum(a)>b:
                    b=sum(a)
        if b==0:
            return max(array)
        return b

python

发表于 2020-04-28 15:08:20 回复(0)

Python

说好了的123

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return None
        result=[]
        for i in range(len(array)):
            for m in range(i,len(array)):
                    result.append(sum(array[i:m+1]))
        return max(result)

发表于 2020-03-30 00:14:17 回复(0)

Python

peter-xbs

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        (851)# write code here
        if not array:
            return 0
        i = 1
        length = len(array)
        prev = array[0]
        M = -float('inf')
        M = prev if prev > M else M
        while i < length:
            cur = array[i]
            if prev > 0:
                cur = cur + prev
            if cur > M:
                M = cur
            prev = cur
            i += 1
        return M
            
                
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        (851)# write code here
        if not array:
            return 0
        length = len(array)
        dp = [0]*length
        dp[0] = array[0]
        M = -float('inf')
        M = M if M > dp[0] else dp[0]
        for i in range(1, length):
            if dp[i-1] > 0:
                dp[i] = dp[i-1]+array[i]
            else:
                dp[i] = array[i]
            if dp[i] > M:
                M = dp[i]
        return M


	 



	### code 2 时间复杂度O(N),空间复杂度O(N)

### code 1 时间复杂度O(N),空间复杂度O(1)

编辑于 2020-03-22 21:16:00 回复(0)

Python

但行好事-莫问前程

暴力求解

将问题划分为对每个数组元素，迭代向后求和最大值问题

对每个数据元素求和的最大值进行筛选，得出所有数据元素中连续求和的最大值

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        (851)# write code here
        def sub_max(item, array):
            mx = item
            s = item
            for i in array:
                s += i
                if s > mx:
                    mx = s
            return mx 
                    
        s_max = array[0]
        for i in range(len(array)):
            item = array.pop(0)
            s_max = sub_max(item,array) if s_max < sub_max(item,array) else s_max
        return s_max

发表于 2020-03-04 09:59:08 回复(0)

Python

牛客447097232号

# -*- coding:utf-8 -*-
"""
题目转换成，以第i个元素结尾时，最大的连续子序列是多少
动态规划: res[i] = max(array[i], res[i-1]+array[i])
也就是说以res[i-1]不大于0时，则不加上之前的序列
"""
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0
        else:
            for i in range(1, len(array)):
                if array[i-1] > 0:
                    array[i] += array[i-1]
            return max(array)


s = Solution()
ans = s.FindGreatestSumOfSubArray([2,8,1,5,9])
print(ans)

编辑于 2020-03-01 14:38:44 回复(0)

Python

朝夕_

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        if not array:
            return 0
        if len(array) == 1:
            return array[0]
        else:
            a = float("-inf")
            for i in range(len(array)-1):
                for j in range(i,len(array)):
                    if a < sum(array[i:j+1]):
                        a = sum(array[i:j+1])
        return int(a)

发表于 2020-02-24 10:31:43 回复(0)

提交观点

问题信息

贪心动态规划

难度：

88条回答 3025收藏 159166浏览

通过挑战的用户

查看代码

松林子木

2023-03-08 10:26:42
牛客42465...

2023-03-03 20:52:51
Elastic...

2023-02-26 11:32:37
牛客10259...

2023-02-24 16:57:17
牛客94801...

2023-02-18 18:10:42

连续子数组的最大和

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题