Leetcode 53. Maximum Subarray

Problem

Given an integer array, find the contiguous subarray that has the largest sum and return that sum value.

A subarray is a contiguous portion of the array. For example, in the array [1, 2, 3, 4], some subarrays include [1, 2], [2, 3, 4], and [1, 2, 3, 4], but [1, 3] is not a valid subarray because the elements are not contiguous.

Requirements

1. Return the sum of the contiguous subarray with the maximum sum
2. Handle arrays containing negative numbers, positive numbers, or a mix of both
3. If all numbers are negative, return the largest (least negative) number
4. Implement an efficient solution that processes the array in a single pass

Constraints

• 1 ≤ nums.length ≤ 105
• -104 ≤ nums[i] ≤ 104
• Target time complexity: O(n)
• Target space complexity: O(1)

Examples

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 of 6

Example 2:

Input: nums = [1] Output: 1 Explanation: With a single element, that element is the answer

Example 3:

Input: nums = [5, 4, -1, 7, 8] Output: 23 Explanation: The entire array [5, 4, -1, 7, 8] has the largest sum of 23

Example 4:

Input: nums = [-3, -2, -5, -1] Output: -1 Explanation: When all numbers are negative, we choose the largest value

Hint 1: Dynamic Thinking At each position, you need to make a decision: should you extend the current subarray by including this element, or should you start a fresh subarray from this element? Think about when it makes sense to "reset" and start over.

Hint 2: Track Running Sum Keep track of the current subarray sum as you iterate through the array. If adding the current element to your running sum makes it worse than just starting fresh with the current element, what does that tell you?

Hint 3: Kadane's Algorithm This is a classic application of Kadane's algorithm. Maintain two values: the maximum sum seen so far globally, and the maximum sum ending at the current position. At each step, decide whether to extend the current sum or start anew.

Full Solution ` def maxSubArray(nums): # Initialize both the global maximum and current sum with the first element max_sum = nums[0] current_sum = nums[0]

# Iterate through the array starting from the second element
for i in range(1, len(nums)):
    # At each position, decide whether to:
    # 1. Extend the current subarray (current_sum + nums[i])
    # 2. Start a new subarray from this element (nums[i])
    # Choose whichever gives a larger sum
    current_sum = max(nums[i], current_sum + nums[i])
    
    # Update the global maximum if current sum is larger
    max_sum = max(max_sum, current_sum)

return max_sum

`

Explanation:

This solution implements Kadane's algorithm, which efficiently finds the maximum subarray sum in linear time.

Algorithm:

1. Initialize max_sum and current_sum with the first element
2. For each subsequent element, decide whether to extend the current subarray or start a new one
3. The key insight: if current_sum + nums[i] is less than nums[i] alone, it means the previous subarray was dragging down the total, so we're better off starting fresh
4. Track the maximum sum encountered throughout the process

Time Complexity: O(n) where n is the length of the array. We make a single pass through the array.

Space Complexity: O(1) as we only use two variables regardless of input size.

Why This Works:

The algorithm works because at each position, we're solving a subproblem: "What's the maximum sum of a subarray ending at this position?" There are only two possibilities:

• The maximum subarray ending here extends from the previous position
• The maximum subarray ending here starts at the current position

By keeping track of both the best sum ending at the current position and the best sum seen overall, we can determine the answer in one pass.