Maximum Subarray

Problem Summary

• Given an input array, return the maximum sum of a subarray
• Input could have negative numbers
• Solve it in $O(n)$ time complexity

Main Concepts Used

• Kadane's Algorithm

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through the input once
• Space: $O(1)$ → Reason: Just storing 2 variables

Code

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

        for i, num in enumerate(nums):
            if not i:
                continue
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)

        return max_sum