Maximum Subarray LeetCode solution in Python

1
# Runtime: 782 ms (Top 6.1%) | Memory: 163.13 MB (Top 6.3%)
2

3

4
class Solution:
5
    def maxSubArray(self, nums: List[int]) -> int:
6
        def kadane(i):
7
            if F[i] != None:
8
                return F[i]
9
            F[i] = max(nums[i], kadane(i - 1) + nums[i])
10
            return F[i]
11

12
        n = len(nums)
13
        F = [None for _ in range(n)]
14
        F[0] = nums[0]
15
        kadane(n - 1)
16
        return max(F)