Maximum Subarray — Kadane's Algorithm Explained [Google, Amazon, Meta]

Problem Statement

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

Examples:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Reason: Subarray [4, -1, 2, 1] has the largest sum = 6

Input:  [1]      → 1
Input:  [5, 4, -1, 7, 8] → 23 (entire array)

Intuition — Kadane's Algorithm
Solutions in All 5 Languages
C
C++
Java
JavaScript
Python
Complexity Analysis
Divide & Conquer Alternative (O(n log n))
Follow-up — Return the Actual Subarray
Variants (FAANG follow-ups)
Key Takeaway

Intuition — Kadane's Algorithm

Core idea: At each position, decide whether to:

Extend the existing subarray (add current element to running sum), or
Start fresh (begin a new subarray from current element)

When does starting fresh win? When the running sum becomes negative — a negative prefix only hurts us.

current = nums[0]
best    = nums[0]

for x in nums[1:]:
    current = max(x, current + x)   ← extend or restart
    best    = max(best, current)

Proof of correctness: If the optimal subarray starts at index i, then for every prefix ending before i, our running sum must have gone negative (otherwise we'd extend backwards, contradicting optimality).

Solutions in All 5 Languages

C

#include <stdio.h>

int maxSubArray(int* nums, int numsSize) {
    int current = nums[0];
    int best    = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        if (current < 0) current = nums[i];
        else             current += nums[i];
        
        if (current > best) best = current;
    }
    return best;
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < (int)nums.size(); i++) {
            cur  = max(nums[i], cur + nums[i]);
            best = max(best, cur);
        }
        return best;
    }
};

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur  = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

JavaScript

function maxSubArray(nums) {
    let cur = nums[0], best = nums[0];
    for (let i = 1; i < nums.length; i++) {
        cur  = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }
    return best;
}

Python

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = best = nums[0]
        for x in nums[1:]:
            cur  = max(x, cur + x)
            best = max(best, cur)
        return best

Complexity Analysis

Approach	Time	Space
Kadane's	O(n)	O(1)
Divide & Conquer	O(n log n)	O(log n)
Brute Force	O(n²)	O(1)

Divide & Conquer Alternative (O(n log n))

For interviews that ask for a D&C solution:

def maxSubArray(nums):
    def helper(l, r):
        if l == r: return nums[l]
        mid = (l + r) // 2
        left  = helper(l, mid)
        right = helper(mid+1, r)
        # max crossing subarray
        lsum = rsum = 0
        cur = 0
        for i in range(mid, l-1, -1): cur += nums[i]; lsum = max(lsum, cur)
        cur = 0
        for i in range(mid+1, r+1): cur += nums[i]; rsum = max(rsum, cur)
        return max(left, right, lsum + rsum)
    return helper(0, len(nums)-1)

Follow-up — Return the Actual Subarray

Track start and end indices:

def maxSubArrayWithIndices(nums):
    cur = best = nums[0]
    start = end = 0; temp_start = 0
    for i in range(1, len(nums)):
        if cur < 0:
            cur = nums[i]; temp_start = i
        else:
            cur += nums[i]
        if cur > best:
            best = cur; start = temp_start; end = i
    return nums[start:end+1], best

Variants (FAANG follow-ups)

Variant	Key Change	Trick
Maximum Sum Circular Subarray	Array is circular	Total sum - min subarray
Maximum Product Subarray	Multiply instead of add	Track min AND max
K-concatenation Maximum Sum	Array repeated k times	Kadane + prefix logic

Key Takeaway

Kadane's pattern — "at each step, decide whether the current choice extends the running computation or resets it" — is the foundation of many DP problems.

Next: Problem 5 — Move Zeroes →