我要招人

去企业版

首页 > 试题广场 >

连续子数组最大和

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

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

给定一个长度为 $n\$ 的数组，数组中的数为整数。

请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。

输入描述:

第一行为一个正整数 ，代表数组的长度。 
第二行为 个整数 ，用空格隔开，代表数组中的每一个数。

输出描述:

连续子数组的最大之和。

示例1

输入

8
1 -2 3 10 -4 7 2 -5

输出

说明

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

示例2

输入

1
2

输出

示例3

输入

1
-10

输出

-10

算法知识视频讲解

Python 3

化骨重生

import sys

n=int(input())

L=list(map(int,input().split()))

k=-1

for i in range(n):

if L[i]>0:

k=i

break

if k==-1:

print(max(L))

elif k==n-1:

print(L[-1])

else:

sum1=0

last=L[k]

for i in range(k,n):

if sum1<0 and L[i]>0:

sum1=0

sum1+=L[i]

if sum1>last:

last=sum1

print(last)

发表于 2023-04-18 14:12:34 回复(0)

Python 3

踏实的大白菜说又不是不能用

class Solution:
    def maxstr(self,n,nums):
        dp = [0]*n 
        dp[0] = nums[0]
        for i in range(1,n):
            dp[i] = max(dp[i-1]+nums[i] , nums[i])
        return max(dp)
n = int(input())
nums = list(map(int,input().split()))
a = Solution()
b = a.maxstr(n,nums)
print(b)

发表于 2022-09-08 16:27:29 回复(0)

Python 3

牛客253248209号

# 使用穷举的方法，但是导致超时，部分不能计算正确
n = int(input())
l = list(map(int,input().split()))
l = l+[0,0]
dp=[]
for i in range(n):
    for k in range(i,n):
        dp.append(sum(l[i:k+1]))
print(max(dp))

发表于 2022-09-02 22:46:38 回复(0)

Python 3

牛客167042955号

n=int(input())
o=input()
if len(o)>2:
m=o.split(' ')
#print(m)
l=[]
for i in m:
if len(i)!=0:
l.append(int(i))
'h=map(int,m) l=list(h)'
#print(l)
for i in range(0,n):#下标
l[i]=0
for j in range(i,n):
sum=l[i]+l[j]
l[i]=sum
l.append(sum)
#print(l)
print(max(l))

else:

print(o[0])

发表于 2022-08-22 13:33:10 回复(0)

Python 3

九方空

def maxcount():
    x=int(input())
    y=input()
    l=y.split(' ')
    m=l[0]
    dp=[]
    dp.append(l[0])
    for i in range(1,x):
        dp.append(max(int(l[i]),int(dp[i-1])+int(l[i])))
        m=max(int(m),int(dp[i]))
    print(m)
maxcount()

发表于 2021-10-19 19:21:27 回复(0)