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

[编程题]连续子数组最大和(ACM版本)

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

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

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

输入描述:

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

输出描述:

连续子数组的最大之和。

示例1

输入

3
3 -4 5

输出

说明

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

示例2

输入

3
4 -3 5

输出

说明

选择 [4,-3,5] 这个子数组。

算法知识视频讲解

Python3

牛客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

# 解法一
_ = 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

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)