连续子数组最大和

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

热度指数：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

算法知识视频讲解

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)