Maximum Subarray

Problem Statement

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

What to notice first

• A subarray must be contiguous — you cannot skip elements.
• You are looking for the largest sum, not the largest array.
• Even if all numbers are negative, you must return the one with the smallest absolute value (least negative).
• The answer is never “no subarray” — you must return at least one element.

Examples

Input	Output	Explanation
[-2, 1, -3, 4, -1, 2, 1, -5, 4]	6	Subarray [4, -1, 2, 1] has the largest sum of 6
[5, 4, -1, 7, 8]	23	Entire array [5, 4, -1, 7, 8] has the sum of 23
[-1]	-1	Only one element, so return that element

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Real-World Applications

Where this pattern appears

• Stock trading — finding the time period with the best cumulative gains.
• Network traffic analysis — identifying busiest periods by summing request counts over time windows.
• Weather analysis — finding consecutive days with the highest average temperature change.
• Budget forecasting — identifying quarters with the highest cumulative cash flow.

Complexity Comparison

Approach	Time	Space	Best When
Brute Force	O(n²)	O(1)	Learning, tiny arrays
Kadane	O(n)	O(1)	General case — fast and simple
Divide & Conquer	O(n log n)	O(log n)	Interview discussion

Which approach should you learn first?

• Pick Kadane for the optimal interview solution — it is simple, O(n), and elegant.
• Pick Brute Force if you are learning how to think about subarrays.
• Pick Divide & Conquer if you want to understand the recursive pattern or are discussing trade-offs.

Best For Speed

Kadane

O(n) time · O(1) space

Learn Pattern

Brute Force

O(n²) time · O(1) space

Divide & Conquer

Recursive

O(n log n) time · O(log n) space

Approach 1: Brute Force

✓ Simple

Check every possible subarray by examining all pairs of start and end indices. For each starting position, consider all possible ending positions and track the maximum sum found.

⏱ Time O(n²) All pairs checked 💾 Space O(1) Constant

Solution Code

Python

maximum_subarray_brute_force.py

from typing import List


def maximum_subarray_brute_force(nums: List[int]) -> int:
    """
    Maximum Subarray - Brute Force approach.

    Time: O(n), Space: O(1) or O(n) depending on approach
    """
    pass


if __name__ == "__main__":
    # Test cases
    pass

C++

maximum_subarray_brute_force.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int maximum_subarray_brute_force(vector<int>& nums) {
        // Maximum Subarray - Brute Force approach
        return 0;
    }
};

int main() {
    return 0;
}

Java

maximum_subarray_brute_force.java

import java.util.*;

class Solution {
    public int maximum_subarray_brute_force(int[] nums) {
        // Maximum Subarray - Brute Force approach
        return 0;
    }

    public static void main(String[] args) {
        // Test cases
    }
}

JavaScript

maximum_subarray_brute_force.js

/**
 * {@param {number[]} nums}
 * {@return {number}}
 */
var maximum_subarrayBruteforce = function(nums) {
    // Maximum Subarray - Brute Force approach
    return 0;
};

if (require.main === module) {
    // Test cases
}

Rust

maximum_subarray_brute_force.rs

pub fn maximum_subarray_brute_force(nums: Vec<i32>) -> i32 {
    // Maximum Subarray - Brute Force approach
    0
}

fn main() {
    // Test cases
}

Go

maximum_subarray_brute_force.go

package main

import "fmt"

func maximum_subarrayBruteforce(nums []int) int {
    // Maximum Subarray - Brute Force approach
    return 0
}

func main() {
    // Test cases
}

Approach 2: Kadane’s Algorithm (Recommended)

★ Recommended

Use dynamic programming to track the maximum sum ending at the current position. If adding the current element to the previous maximum sum is worse than starting fresh, restart from the current element.

⏱ Time O(n) Single pass 💾 Space O(1) Constant

Solution Code

Python

maximum_subarray_kadane.py

from typing import List


def maximum_subarray_kadane(nums: List[int]) -> int:
    """
    Maximum Subarray - Kadane approach.

    Time: O(n), Space: O(1) or O(n) depending on approach
    """
    pass


if __name__ == "__main__":
    # Test cases
    pass

C++

maximum_subarray_kadane.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int maximum_subarray_kadane(vector<int>& nums) {
        // Maximum Subarray - Kadane approach
        return 0;
    }
};

int main() {
    return 0;
}

Java

maximum_subarray_kadane.java

import java.util.*;

class Solution {
    public int maximum_subarray_kadane(int[] nums) {
        // Maximum Subarray - Kadane approach
        return 0;
    }

    public static void main(String[] args) {
        // Test cases
    }
}

JavaScript

maximum_subarray_kadane.js

/**
 * {@param {number[]} nums}
 * {@return {number}}
 */
var maximum_subarrayKadane = function(nums) {
    // Maximum Subarray - Kadane approach
    return 0;
};

if (require.main === module) {
    // Test cases
}

Rust

maximum_subarray_kadane.rs

pub fn maximum_subarray_kadane(nums: Vec<i32>) -> i32 {
    // Maximum Subarray - Kadane approach
    0
}

fn main() {
    // Test cases
}

Go

maximum_subarray_kadane.go

package main

import "fmt"

func maximum_subarrayKadane(nums []int) int {
    // Maximum Subarray - Kadane approach
    return 0
}

func main() {
    // Test cases
}

Approach 3: Divide and Conquer

🎯 Interview Favourite

Divide the array into two halves and recursively find the maximum subarray in each half. The answer is either in the left half, right half, or crosses the midpoint.

⏱ Time O(n log n) Recursive depth 💾 Space O(log n) Call stack

Solution Code

Python

maximum_subarray_divide_and_conquer.py

from typing import List


def maximum_subarray_divide_and_conquer(nums: List[int]) -> int:
    """
    Maximum Subarray - Divide And Conquer approach.

    Time: O(n), Space: O(1) or O(n) depending on approach
    """
    pass


if __name__ == "__main__":
    # Test cases
    pass

C++

maximum_subarray_divide_and_conquer.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int maximum_subarray_divide_and_conquer(vector<int>& nums) {
        // Maximum Subarray - Divide And Conquer approach
        return 0;
    }
};

int main() {
    return 0;
}

Java

maximum_subarray_divide_and_conquer.java

import java.util.*;

class Solution {
    public int maximum_subarray_divide_and_conquer(int[] nums) {
        // Maximum Subarray - Divide And Conquer approach
        return 0;
    }

    public static void main(String[] args) {
        // Test cases
    }
}

JavaScript

maximum_subarray_divide_and_conquer.js

/**
 * {@param {number[]} nums}
 * {@return {number}}
 */
var maximum_subarrayDivideandconquer = function(nums) {
    // Maximum Subarray - Divide And Conquer approach
    return 0;
};

if (require.main === module) {
    // Test cases
}

Rust

maximum_subarray_divide_and_conquer.rs

pub fn maximum_subarray_divide_and_conquer(nums: Vec<i32>) -> i32 {
    // Maximum Subarray - Divide And Conquer approach
    0
}

fn main() {
    // Test cases
}

Go

maximum_subarray_divide_and_conquer.go

package main

import "fmt"

func maximum_subarrayDivideandconquer(nums []int) int {
    // Maximum Subarray - Divide And Conquer approach
    return 0
}

func main() {
    // Test cases
}

Common mistakes

Watch for these pitfalls

• Mistake 1 — explain what to watch for
• Mistake 2 — explain what to watch for
• Mistake 3 — explain what to watch for

Related Problems

• Two Sum ↗ Easy #1
• Contains Duplicate ↗ Easy #217

Interview Tips

Key discussion points

• Trade-offs between different approaches
• Edge cases to consider
• Possible follow-up questions
• How to extend the solution