# 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)