Maximum Subarray

The problem description can be found in LeetCode.

Approach

Here, we can apply the well-known Kadane's algorithm.

Solution

from typing import List


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

        best_sum = curr_sum = nums[0]

        for num in nums[1:]:
            curr_sum = max(num, curr_sum + num)
            best_sum = max(best_sum, curr_sum)

        return best_sum

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the nums list.