LeetEye LeetEye
Medium Greedy ~5 min

Maximum Subarray

greedy maximum-subarray

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Examples

Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
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
Key Insight

Kadane's Algorithm: If current sum becomes negative, start fresh.

Kadane's: current_sum = max(nums[i], current_sum + nums[i]). If current sum is negative, start fresh.

How to Approach This Problem

Pattern Recognition: When you see keywords like maximum subarray greedy, think Greedy.

Step-by-Step Reasoning

1 At each element, we decide:
Answer: Include in current subarray or start new
Either extend current subarray or this element starts a new one.
2 We start a new subarray at nums[i] when:
Answer: current_sum + nums[i] < nums[i]
If adding to current sum makes it worse than just nums[i], start fresh.
3 current_sum + nums[i] < nums[i] simplifies to:
Answer: current_sum < 0
Subtract nums[i] from both sides: current_sum < 0.
4 We need to track:
Answer: Both
Current sum for building subarray, max sum for the answer.
5 For [-3, -1, -2]:
Answer: Return -1 (largest single element)
Must have at least one element. Best is the largest (least negative).

Solution

def maxSubArray(nums: List[int]) -> int:
    max_sum = nums[0]
    current_sum = nums[0]
    
    for i in range(1, len(nums)):
        # Either extend current subarray or start new
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye