大子序列和"/>
【python】最大子序列和
题目描述:
给定一个整数数组,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。输入格式:
第一行输入包含一个整数 n,表示数组的长度。
第二行输入包含 n 个整数,表示数组元素,相邻两个数之间用空格分隔。输出格式:
输出一个整数,表示数组中的最大连续子数组的和。限制:
1. 1<=n<=10的6次方,即数组的长度 n 限制在 1 到 1000000 之间。
2. 数组中的每个元素都是整数,且其绝对值不超过 10的4次方。
# 思路:动态规划
# 1. 从左到右遍历,记录当前最大字段和
# 2. 如果当前最大字段和小于0,则舍弃,从下一个元素开始重新计算
# 3. 如果当前最大字段和大于0,则继续累加
# 4. 每次累加都与最大字段和比较,如果大于最大字段和,则更新最大字段和
# 5. 遍历结束后,返回最大字段和def maxSubArray(nums):maxSum = nums[0] # 初始化最大子段和为数组的第一个元素curSum = 0 # 当前子段和初始化为0# 遍历数组中的每个元素for i in range(len(nums)):# 如果当前子段和小于0,则重置为当前元素值if curSum < 0:curSum = nums[i]else:# 否则,累加当前元素值到当前子段和curSum += nums[i]# 更新最大子段和if curSum > maxSum:maxSum = curSum# 返回计算后的最大子段和return maxSum# 从用户那里接收输入
n = int(input()) # 用户输入数组长度
nums = list(map(int, input().split())) # 用户输入数组本身,以空格分隔
print(maxSubArray(nums)) # 打印并返回最大子段和
更多推荐
【python】最大子序列和
发布评论