class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        n = len(nums)
        dp = [0]*(n+1)
        max_so_far = -math.inf

        for i in range(1, n+1):
            dp[i] = max(dp[i-1] + nums[i-1], nums[i-1])
            max_so_far = max(dp[i], max_so_far)

        return max_so_far


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        prev1 = 0
        max_so_far = -math.inf

        for n in nums:

            max_ending_here = max(prev1 + n, n)
            # made the mistake here of including prev1: max_ending_here = max(prev1 + n, n, prev1)
            # if prev1 is included above, it defeates the entire purpose of a continguous array
            max_so_far = max(max_ending_here, max_so_far)
            prev1 = max_ending_here

        return max_so_far

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        current_sum = 0
        max_so_far = -math.inf

        for n in nums:

            max_ending_here = max(current_sum + n, n)
            # made the mistake here of including prev1: max_ending_here = max(prev1 + n, n, prev1)
            # if prev1 is included above, it defeates the entire purpose of a continguous array
            max_so_far = max(max_ending_here, max_so_far)
            current_sum = max_ending_here

        return max_so_far