You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
lavos/python/cap4/work4.py

19 lines
887 B

# work4 求最大字字段和(同例15的解法,此处为python版本写法)
# o(n)时间复杂度,o(1)空间。
# 一路扫描,currMaxSum为当前位置为止的最大和,当到下一个位置时,判断当前数字num加上currMaxSum是否会导致比当前num还小,
# 如果当前数字num加上currMaxSum是否会导致比当前num还小,则说明最大的和不应从前面开始,而是*至少*应当从当前的数字开始
# 下一步比较结果与当前的最大和哪个大,取更大的作为结果
def findMaxSum(nums: list[int]) -> int:
result = nums[0]
currMaxSum = nums[0]
for i in range(1, len(nums)):
num = nums[i]
currMaxSum = max(currMaxSum+num, num)
result = max(result, currMaxSum)
return result
# test
nums = [-2, 11, -4, -9, 13, -5, 7, -3]
result = findMaxSum(nums)
print("最大子段和:", result)