# How to Solve the Maximum Subarray Problem Using Kadane’s Algorithm

> Master the Maximum Subarray problem with Kadane's algorithm. Learn this efficient O(n) solution to find the largest sum subarray quickly. Improve your coding skills today.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**Kadane’s algorithm solves the Maximum Subarray problem in O(n) time by tracking the maximum sum ending at each position and the global maximum seen so far.**

The Maximum Subarray problem is a fundamental algorithmic challenge that appears frequently in technical interviews at companies like LinkedIn and Facebook. In the open-source repository **kdn251/interviews**, you’ll find multiple implementations of Kadane’s algorithm that demonstrate both explicit dynamic programming approaches and space-optimized solutions. Understanding these implementations provides a solid foundation for solving not just the classic array problem, but also variations like the best time to buy and sell stock.

## Understanding the Maximum Subarray Problem

The problem asks you to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. Because the array may contain negative numbers, the solution must intelligently decide when to start a new subarray versus extending the current one. This is exactly what **Kadane’s algorithm** accomplishes through a greedy dynamic programming strategy.

## Kadane’s Algorithm Implementation in kdn251/interviews

The repository contains two distinct implementation styles that illustrate the evolution from textbook DP to production-ready optimization.

### DP Approach with Auxiliary Array

In [`company/linkedin/MaximumSubarray.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/MaximumSubarray.java) and [`leetcode/array/MaximumSubarray.java`](https://github.com/kdn251/interviews/blob/main/leetcode/array/MaximumSubarray.java), the solution uses an explicit `dp` array to make the recurrence relation visible:

```

dp[i] = nums[i] + (dp[i‑1] > 0 ? dp[i‑1] : 0)

```

This formulation clearly shows the decision at each index: extend the previous subarray only if it contributes positively to the sum; otherwise, discard it and start fresh at the current element. While this approach uses **O(n)** additional space for the `dp` array, it explicitly mirrors the mathematical definition of the problem.

### Space-Optimized Kadane’s Algorithm

A more memory-efficient implementation appears in [`company/facebook/BestTimeToBuyAndSellStock.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/BestTimeToBuyAndSellStock.java) (lines 18‑32), where the same core logic is applied to price differences without auxiliary storage. This version uses two variables—`current` (the maximum subarray ending here) and `maxSoFar` (the global maximum)—demonstrating that Kadane’s algorithm requires only **O(1)** space.

## Step-by-Step Algorithm Walkthrough

The algorithm processes the array in a single pass with three straightforward steps:

1. **Initialize** both `maxSoFar` and `current` to the first element `nums[0]`.
2. **Iterate** from the second element to the end:
   - Update `current` to be the maximum of the current element alone (`nums[i]`) or the current element extended by the previous subarray (`current + nums[i]`).
   - Update `maxSoFar` if `current` exceeds it.
3. **Return** `maxSoFar` as the maximum sum of any contiguous subarray.

## Complete Java Implementation

Here is the space-optimized Kadane’s algorithm as derived from the repository’s implementation patterns:

```java
/**
 * Kadane's algorithm – O(n) time, O(1) space.
 *
 * @param nums input integer array (must contain at least one element)
 * @return maximum sum of any contiguous sub‑array
 */
public int maxSubArrayKadane(int[] nums) {
    int maxSoFar = nums[0];
    int current = nums[0];

    for (int i = 1; i < nums.length; i++) {
        // Either extend the previous sub‑array or start a new one at i
        current = Math.max(nums[i], current + nums[i]);
        // Update global maximum if needed
        maxSoFar = Math.max(maxSoFar, current);
    }
    return maxSoFar;
}

```

This implementation eliminates the `dp` array while preserving the mathematical correctness of the recurrence relation, exactly as demonstrated in the Facebook stock trading solution.

## Complexity Analysis

- **Time Complexity:** **O(n)** where n is the length of the input array, since the algorithm makes exactly one pass through the data.
- **Space Complexity:** **O(1)** for the optimized version (only two integer variables), or **O(n)** for the DP version that stores intermediate results in an auxiliary array.

## Summary

- The **Maximum Subarray problem** seeks the contiguous subarray with the largest sum in a given integer array.
- **Kadane’s algorithm** solves this in linear time by maintaining the best subarray ending at the current index and the global maximum.
- The **kdn251/interviews** repository provides both explicit DP implementations in [`company/linkedin/MaximumSubarray.java`](https://github.com/kdn251/interviews/blob/main/company/linkedin/MaximumSubarray.java) and [`leetcode/array/MaximumSubarray.java`](https://github.com/kdn251/interviews/blob/main/leetcode/array/MaximumSubarray.java), and a space-optimized version in [`company/facebook/BestTimeToBuyAndSellStock.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/BestTimeToBuyAndSellStock.java).
- The space-optimized approach uses only two variables (`current` and `maxSoFar`), achieving **O(1)** space complexity while remaining **O(n)** time.

## Frequently Asked Questions

### What is the recurrence relation for Kadane’s algorithm?

The recurrence relation is `dp[i] = nums[i] + max(dp[i-1], 0)`, which means the maximum subarray ending at index `i` equals the current element plus the maximum of zero or the maximum subarray ending at `i-1`. In code, this is typically written as `current = Math.max(nums[i], current + nums[i])`.

### Can Kadane’s algorithm handle arrays with all negative numbers?

Yes. By initializing `maxSoFar` and `current` to the first element rather than zero, the algorithm correctly returns the largest (least negative) number when all values are negative. This initialization pattern is used in both the LinkedIn and LeetCode solutions within the repository.

### What is the difference between the DP and space-optimized versions?

The DP version in [`MaximumSubarray.java`](https://github.com/kdn251/interviews/blob/main/MaximumSubarray.java) uses an auxiliary array to store the maximum sum ending at each index, making the logic easier to trace and debug. The space-optimized version in [`BestTimeToBuyAndSellStock.java`](https://github.com/kdn251/interviews/blob/main/BestTimeToBuyAndSellStock.java) (lines 18‑32) collapses the DP table into two variables, reducing space from **O(n)** to **O(1)** while maintaining the same **O(n)** time complexity.

### How does the Maximum Subarray problem relate to stock trading?

The "Best Time to Buy and Sell Stock" problem reduces to Maximum Subarray when you transform the price array into an array of daily price differences. The maximum profit equals the maximum subarray sum of these differences, which is why [`company/facebook/BestTimeToBuyAndSellStock.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/BestTimeToBuyAndSellStock.java) implements Kadane’s algorithm to solve it efficiently.