Medium Dynamic Programming ⭐ Classic Algorithm

Maximum Subarray — Kadane's Algorithm Explained (Python, C, JS)

Problem Statement

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

Example

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output: 6 # subarray [4, -1, 2, 1]

Time Complexity

O(n)

Space Complexity

O(1)

The Intuition

Kadane: track current_sum. If current_sum drops below 0, reset it to 0 (a negative prefix only hurts us). Update max_sum each step.

Solution Code

def maxSubArray(nums):
    max_sum = nums[0]
    curr = 0
    for n in nums:
        curr = max(n, curr + n)
        max_sum = max(max_sum, curr)
    return max_sum

int maxSubArray(int* nums, int n) {
    int max_s = nums[0], curr = 0;
    for (int i = 0; i < n; i++) {
        if (curr < 0) curr = 0;
        curr += nums[i];
        if (curr > max_s) max_s = curr;
    }
    return max_s;
}

function maxSubArray(nums) {
    let max = nums[0], curr = 0;
    for (const n of nums) {
        curr = Math.max(n, curr + n);
        max = Math.max(max, curr);
    }
    return max;
}

Frequently Asked Questions

Q: What if all numbers are negative?

Initialise max_sum = nums[0]. Kadane will correctly pick the least-negative single element.

Practice These Problems in a Real Curriculum

DoxaTech Hub's 10-month programme covers Data Structures, Algorithms, Python, C, SQL, and Full-Stack Development through 40 weeks of real, graded projects.

Get Started → More Problems