Solutions

# Brute force, or Kadane algorithm (either simple loop or sliding window)
# kadane

# Brute force: O(n^2) time, O(1) space
def maxSubArray(nums: list[int]) -> int:
    maxsum = -9999
    for i in range(len(nums)):
        cursum = 0
        for j in range(i, len(nums)):
            cursum += nums[j]
            maxsum = max(maxsum, cursum)
    return maxsum

# Kadane with sliding window: O(n) time, O(1) space
def maxSubArray(nums: list[int]) -> int:
    maxsum = nums[0]
    cursum = 0
    maxl, maxr = 0, 0
    l, r = 0, 0

    for r in range(len(nums)):
        if cursum < 0:
            cursum = 0
            l = r

        cursum += nums[r]

        if cursum > maxsum:
            maxsum = cursum
            maxl, maxr = l, r

    res = 0
    for i in range(maxl, maxr + 1):
        res += nums[i]
    return res
    
# Kadane: O(n) time, O(1) space
def maxSubArray(nums: list[int]) -> int:
    maxsum = nums[0]
    cursum = 0

    for i in range(len(nums)):
        cursum = max(cursum, 0) # a negative cursum would only be counterproductive
        cursum += nums[i]
        maxsum = max(cursum, maxsum)

    return maxsum

# Dynamic programming top-down: O(n) time, O(n) space
def maxSubArray(nums: list[int]) -> int:
    memo = [[None] * 2 for _ in range(len(nums) + 1)]

    def dfs(i, flag):
        if i == len(nums):
            return 0 if flag else -1e6
        if memo[i][flag] is not None:
            return memo[i][flag]
        if flag:
            memo[i][flag] = max(0, nums[i] + dfs(i + 1, True))
        else:
            memo[i][flag] = max(dfs(i + 1, False),
                                nums[i] + dfs(i + 1, True))
        return memo[i][flag]

    return dfs(0, False)