Maximum Subarray - Video Solutions

Problem Overview: Given an integer array nums, find the contiguous subarray with the largest possible sum and return that sum. The challenge is identifying the best subarray without checking every possible range.

Approach 1: Kadane's Algorithm (O(n) time, O(1) space)

Kadane's Algorithm scans the array once while maintaining the maximum sum ending at the current position. At each index, you decide whether to extend the previous subarray (current_sum + nums[i]) or start a new subarray at the current element. This works because any negative running sum only hurts future results, so resetting when the sum becomes smaller than the current element keeps the best candidate alive. You track a global maximum while iterating. The algorithm uses only two variables and runs in linear time, making it the most efficient and commonly expected solution for this problem.

The idea closely relates to dynamic programming. Each state represents the best subarray ending at index i, computed from the state at i-1. Because the recurrence depends only on the previous value, the DP table compresses into constant space.

Approach 2: Divide and Conquer (O(n log n) time, O(log n) space)

The divide and conquer strategy splits the array into two halves recursively. For each segment, compute three values: the best subarray entirely in the left half, the best entirely in the right half, and the best crossing the midpoint. The crossing sum is calculated by expanding from the midpoint outward to capture the maximum suffix of the left side and maximum prefix of the right side. The final answer for that segment is the maximum of these three candidates.

This method demonstrates how the problem can be broken into independent subproblems, a common pattern in divide and conquer algorithms. Although slower than Kadane's algorithm due to recursive splitting and merging, it helps build intuition about how subarray boundaries interact across partitions. The recursion depth contributes O(log n) auxiliary space.

Both approaches operate on a simple array structure and rely on tracking partial sums rather than enumerating all subarrays.

Recommended for interviews: Kadane's Algorithm is the expected answer. Interviewers want to see that you recognize the linear-time dynamic programming pattern and can derive the recurrence max(nums[i], current_sum + nums[i]). Mentioning the divide and conquer solution shows deeper understanding of the problem structure, but implementing Kadane's algorithm cleanly demonstrates strong algorithmic intuition and optimal complexity.