Leetcode 53. Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maximum = nums[0]
        total = 0
        for i in range(len(nums)):
            total += nums[i]
            maximum = max(total, maximum)
            if total < 0:
                total = 0
        return maximum

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        maximum = dp[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
            maximum = max(maximum, dp[i])
        return maximum