Time complexity: O(n)
Space complexity: O(n)

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

        #f[i]: the sum of subsequence which satisfies:
        # 1). the last element is List[i]
        # 2). maximum sum


        f = [nums[0]]
        res = nums[0]

        for i in range(1, n):
            f.append(max(f[-1] + nums[i], nums[i]))
            res = max(res, f[-1])

        return res

Time complexity: O(n)
Space complexity: O(1)

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

        n = len(nums)

        #f: the sum of subsequence which satisfies:
        # 1). the last element is List[i]
        # 2). maximum sum


        f = nums[0]
        res = nums[0]

        for i in range(1, n):

            if f < 0:
                f = nums[i]
            else:
                f += nums[i]

            res = max(res, f)

        return res