LeetCode Solutions Blog

Maximum Subarray

Number: 53

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest sum and return its sum.

Key Insights

Use Kadane's Algorithm to solve the problem in O(n) time.
Keep track of a running sum (currentSum) and update it with the maximum between the current element and the sum including the current element.
The maximum sum encountered during the iteration (maxSum) is the answer.
A divide and conquer approach also exists, splitting the array and merging solutions, but Kadane's method is optimal for this problem.

Space and Time Complexity

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

Solution

The solution uses Kadane's Algorithm. Iterate over the array while maintaining two variables: currentSum, which tracks the maximum subarray sum ending at the current position, and maxSum, which stores the best sum seen so far. For each element, update currentSum to be either the current element or the sum of currentSum and the current element, whichever is higher. Update maxSum accordingly. This approach efficiently computes the maximum contiguous subarray sum in a single pass.

Code Solutions

# Python solution using Kadane's Algorithm
def maxSubArray(nums):
    # Initialize currentSum and maxSum to the first element
    current_sum = max_sum = nums[0]
    # Traverse through the array starting from the second element
    for num in nums[1:]:
        # If current_sum + num is less than num, restart at num
        current_sum = max(num, current_sum + num)
        # Update max_sum if current_sum is greater
        max_sum = max(max_sum, current_sum)
    return max_sum

# Example usage
if __name__ == "__main__":
    sample = [-2,1,-3,4,-1,2,1,-5,4]
    print(maxSubArray(sample))  # Output: 6