首页 > 试题广场 >

连续子数组最大和(ACM版本)

[编程题]连续子数组最大和(ACM版本)
  • 热度指数：30769 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 的数组，数组中的数为整数。
请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。

输入描述:
第一行为一个正整数 ，代表数组的长度。 1\leq n \leq 2 \cdot10^5
第二行为 个整数 a_i，用空格隔开，代表数组中的每一个数。


输出描述:
连续子数组的最大之和。
示例1

输入

3
3 -4 5

输出

5

说明

选择 [5] 这个子数组即可。
示例2

输入

3
4 -3 5

输出

6

说明

选择 [4,-3,5] 这个子数组。
算法知识视频讲解
添加回答
Python3
牛客351477353号头像 牛客351477353号 
n = int(input())
a=list(map(int,input().split()))
dp=[0 for _ in range(n)]
for i in range(n):
    dp[i]=max(a[i],dp[i-1]+a[i])
print(max(dp))


发表于 2025-05-08 11:08:38 回复(0)
Python3
LeoAlan头像 LeoAlan 
# 解法一
_ = input()
arr = list(map(int, input().split()))

# 初始化s为从第一个元素前开始连续相加的值
s = 0
# 初始化res为第一个元素的值
res = arr[0]

# 遍历数组
for i in arr:
    # 更新s
    s += i
    # 如果更新后的s比res大，则赋值给res
    res = max(s, res)
    # 如果更新后的s小于0，则清空值，从下一个元素开始更新
    s = max(s, 0)

# 最后res即为连续子数组的最大值
print(res)


# 解法二
n = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]
# 遍历数组
for i in range(1, n):
    # 连加后的值与下一个值作比较，如果连加后比较大，则不取下一个值；如果下一个值比较大，则从下一个值算起
    dp.append(max(arr[i], dp[i - 1] + arr[i]))

print(max(dp))

发表于 2023-10-13 10:02:44 回复(0)
Python3
Namely头像 Namely 
import sys

nums = []
for line in sys.stdin:
    a = line.split()
    nums = a

m = len(nums)
# 定义dp[i]为选中第i元素的子数据最大值
# 输出为max(dp[1],...,dp[m])
# dp方程：dp[i+1] = max(dp[i] + nums[i], nums[i])
dp = [0] * (m+1)
max_res = -9999
for i in range(m):
    dp[i+1] = max(dp[i] + int(nums[i]), int(nums[i]))
    max_res = max(max_res, dp[i+1])
print(max_res)

发表于 2023-03-16 16:22:25 回复(0)
Python3
亦人头像 亦人
n = int(input().strip())
nums = input().strip().split(' ')
nums = list(map(int, nums))
for i in range(1, n):
    nums[i] = max(nums[i-1]+nums[i], nums[i])
print(max(nums))
发表于 2022-03-12 23:21:24 回复(0)
提交观点

问题信息

难度：
5条回答 1708浏览

热门推荐

通过挑战的用户

查看代码

相关试题

连续子数组最大和(ACM版本)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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