首页 > 试题广场 >

连续子数组的最大和

[编程题]连续子数组的最大和
  • 热度指数：648748 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:



要求:时间复杂度为 ，空间复杂度为
进阶:时间复杂度为 ，空间复杂度为
示例1

输入

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

输出

18

说明

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

输入

[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号头像 牛客930331173号
首先注意题目是要求“连续”，既索引必须是0，1，2，3/3，4，5这样的，不能是2，3，5之类的。
所以由此可以使用dp解决。
设dp[i]为以下标i元素结尾的最大和
递推式：dp[i]=max(xi+dp[i-1],xi)
初始状态 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号头像 牛客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号头像 牛客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头像 火树银花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头像 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头像 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头像 liucr.baozi

1.子问题拆分：表示第个字符结尾的的最大子序和，状态有三种情况：个和加上，，中的最大值，其值为
2.其实就是针对前个的最大和选择和不选择的问题，在位置处三种选择，加上前项的最大和，从开始从新加，从开始从新算

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头像 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号头像 牛客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头像 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头像 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头像 说好了的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头像 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
但行好事-莫问前程头像 但行好事-莫问前程
暴力求解
  1. 将问题划分为对每个数组元素，迭代向后求和最大值问题
  2. 对每个数据元素求和的最大值进行筛选，得出所有数据元素中连续求和的最大值 
    # -*- 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号头像 牛客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条回答 155563浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号