#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/maximum-subarray

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/maximum-subarray

Repovive

Maximum Subarray (Kadane's Algorithm) - Algorithm Tutorial | Repovive | Repovive

Repovive.

Back to Algorithms

Maximum Subarray (Kadane's Algorithm) Algorithm Tutorial

easyArray Techniques1 min read1 sections

Learn

Kadane's Algorithm

Kadane's Algorithm finds the maximum sum of any contiguous subarray in $O(n)$ time with a single pass. It's a classic example of dynamic programming with $O(1)$ space.

At each position, you decide whether to extend the previous subarray or start a new one. You extend if the previous sum is positive.

function maxSubarraySum(arr, n):
    maxSum = arr[0]
    currentSum = arr[0]

    for i from 1 to n - 1:
        currentSum = max(arr[i], currentSum + arr[i])
        maxSum = max(maxSum, currentSum)

    return maxSum

If your $currentSum$ becomes negative, starting fresh at the current element is always better than carrying the negative sum forward.

Practice this Algorithm

Apply what you learned by solving the practice problem for Maximum Subarray (Kadane's Algorithm).

Go to Practice Problem

Related Algorithms

Prefix Sum (Range Sum Query)

easy1 min

function maxSubarrayWithIndices(arr, n):
    maxSum = arr[0]
    currentSum = arr[0]
    start = 0
    end = 0
    tempStart = 0

    for i from 1 to n - 1:
        if arr[i] > currentSum + arr[i]:
            currentSum = arr[i]
            tempStart = i
        else:
            currentSum = currentSum + arr[i]
        if currentSum > maxSum:
            maxSum = currentSum
            start = tempStart
            end = i

    return (maxSum, start, end)