import math
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Kadane's Algorithm 卡登算法
        # 定義全局最大和與局部最大和
        global_max_sum = -math.inf
        local_max_sum = 0 
        # 遍歷序列
        for num in nums:
            # 更新局部最大解
            local_max_sum += num
            # 更新全局最大解
            global_max_sum = local_max_sum if global_max_sum < local_max_sum else global_max_sum
            # 假如小於0，直接歸零，因為負數加上去，局部最大解必定數值變小
            if local_max_sum < 0 : local_max_sum=0
        # 回傳全局
        return global_max_sum