# 다이나믹 프로그래밍 풀이
def maxSubArray(self, nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1] if nums[i - 1] > 0 else 0
    return max(nums)

# 카데인 알고리즘 풀이
def maxSubArray(self, nums):
    best_sum = -sys.maxsize
    current_sum = 0
    for num in nums:
        current_sum = max(num, current_sum + num)
        best_sum = max(best_sum, current_sum)
    return best_sum
