【python】最大子序列和

大子序列和"/>

【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))  # 打印并返回最大子段和