leetcode-53 Maximum Subarray

[53] Maximum Subarray

Key Concept: Kadane's Algorithm - A fundamental dynamic programming approach for finding the maximum sum of a contiguous subarray. The core idea is to keep track of the maximum sum ending at each position.

Algorithm: At each position, decide whether to extend the existing subarray or start a new one. If the current sum becomes negative, it's better to start fresh.

# Given an integer array nums, find the subarray with the largest sum, and return its sum.
#
# Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: The subarray [4,-1,2,1] has the largest sum 6.
#
# Example 2:
# Input: nums = [1]
# Output: 1
#
# Example 3:
# Input: nums = [5,4,-1,7,8]
# Output: 23
#
# Constraints:
# 1 <= nums.length <= 10^5
# -10^4 <= nums[i] <= 10^4

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # Kadane's Algorithm
        # cur_sum tracks the maximum sum ending at current position
        # max_sum tracks the overall maximum sum found so far

        cur_sum = max_sum = nums[0]

        for i in range(1, len(nums)):
            # Either extend the existing subarray or start new
            cur_sum = max(nums[i], cur_sum + nums[i])
            max_sum = max(max_sum, cur_sum)

        return max_sum

# Time Complexity: O(n) - single pass through array
# Space Complexity: O(1) - only using two variables