LeetCode 53: Maximum Subarray — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Array | Dynamic Programming | Divide and Conquer

The Problem

Find the contiguous subarray within a one-dimensional array of numbers that has the largest sum and return that sum.

Approach

This solution uses Kadane's algorithm, a dynamic programming approach that maintains a running sum of the current subarray. At each element, we decide whether to start a new subarray from the current element or extend the existing subarray by comparing the current element with the sum of the current element and the previous subarray sum.

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

Code

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

        for num in nums:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)

        return max_sum