首页 > 试题广场 >

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

[编程题]连续子数组最大和(ACM版本)
  • 热度指数:30514 时间限制: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] 这个子数组。
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)
# 解法一
_ = 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)
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)
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)