Maximum Subarray Sum using Kadane's Algorithm

Given an array of integers (which may include negative numbers), your task is to find the maximum sum of any contiguous subarray.

This problem is also known as the Maximum Subarray Problem.

• You must return the maximum sum possible by choosing a continuous range of elements from the array.
• If the array is empty, return 0.

Use Kadane's Algorithm to solve it efficiently in linear time.

Step-by-Step Solution to Maximum Subarray Sum Problem

Understanding the Problem

We are given an array of integers. Our task is to find the maximum sum of a contiguous subarray. That means we must select a subarray (a sequence of elements that appear consecutively) such that the sum of its elements is as large as possible.

We’ll explore this problem step-by-step using examples, and then apply a proven technique called Kadane’s Algorithm to solve it efficiently.

Let's Begin with an Example

Consider the array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We need to find a contiguous subarray that gives the highest sum. Visually exploring this array, we notice that the subarray [4, -1, 2, 1] adds up to 6, which is the maximum possible sum of any contiguous subarray in this case.

Step-by-Step Approach

We start scanning the array from left to right, keeping track of two variables:

• currentSum: The sum of the current subarray being considered
• maxSum: The highest sum found so far

At each element, we decide:

• Should we include this element in the current subarray?
• Or start a new subarray starting from this element?

This decision is made by taking the maximum of:

And then we update:

Intuition for Beginners

If the previous sum is helping us grow (i.e., it's positive), we add the current number to it. But if the previous sum is dragging us down (i.e., it’s negative), we just start fresh from the current number. We always keep track of the maximum we've seen so far.

Understanding Edge Cases

1. All Positive Numbers

Input: [1, 2, 3, 4]
Every number is good for the sum, so we take the whole array. Result = 10

2. All Negative Numbers

Input: [-3, -2, -1]
All sums are negative, so the least negative (i.e., closest to zero) single number is the best. Result = -1

3. Mixed Positive and Negative

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Kadane’s Algorithm picks [4, -1, 2, 1] as the best subarray. Result = 6

4. Zeros or Zero as Maximum

Input: [0, 0, 0] or [-2, -1, 0, -3]
Sometimes zero is the best possible sum, especially when no positive numbers exist. Result = 0

5. Single Element Array

Input: [5] or [-4]
The only element is the result. Result = the element itself

6. Empty Array

Input: []
There are no elements to consider. By convention, the result is 0 or may be undefined depending on the context.

Why Kadane’s Algorithm Works So Well

Instead of trying all possible subarrays (which takes O(n²) time), Kadane’s Algorithm goes through the array just once – that’s O(n) time!

It continuously maintains the best sum seen so far and handles all types of arrays—positive, negative, mixed, zero, or even empty. That's why it's one of the most elegant algorithms in dynamic programming!

1. Given an integer array arr.
2. Initialize two variables: max_sum and current_sum with the value of the first element.
3. Iterate through the array starting from index 1.
4. At each step, update current_sum as the maximum of the current element or current_sum + current_element.
5. Update max_sum if current_sum is greater than max_sum.
6. After the loop, return max_sum as the result.

#include <stdio.h>

int maxSubarraySum(int arr[], int n) {
    int maxSum = arr[0], currentSum = arr[0];
    for (int i = 1; i < n; i++) {
        currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] : arr[i];
        maxSum = (maxSum > currentSum) ? maxSum : currentSum;
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Subarray Sum: %d\n", maxSubarraySum(arr, n));
    return 0;
}

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

int maxSubarraySum(const vector<int>& arr) {
    int maxSum = arr[0], currentSum = arr[0];
    for (size_t i = 1; i < arr.size(); i++) {
        currentSum = max(arr[i], currentSum + arr[i]);
        maxSum = max(maxSum, currentSum);
    }
    return maxSum;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum Subarray Sum: " << maxSubarraySum(arr) << endl;
    return 0;
}

def max_subarray_sum(arr):
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Sample Input
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray_sum(arr))

public class MaxSubarraySum {
    public static int maxSubarraySum(int[] arr) {
        int maxSum = arr[0], currentSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubarraySum(arr));
    }
}

function maxSubarraySum(arr) {
    let maxSum = arr[0];
    let currentSum = arr[0];
    for (let i = 1; i < arr.length; i++) {
        currentSum = Math.max(arr[i], currentSum + arr[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

// Sample Input
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum Subarray Sum:", maxSubarraySum(arr));

package main

import (
    "fmt"
)

func maxSubarraySum(arr []int) int {
    maxSum, currentSum := arr[0], arr[0]
    for i := 1; i < len(arr); i++ {
        if currentSum+arr[i] > arr[i] {
            currentSum += arr[i]
        } else {
            currentSum = arr[i]
        }
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    return maxSum
}

func main() {
    arr := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    fmt.Println("Maximum Subarray Sum:", maxSubarraySum(arr))
}

fn max_subarray_sum(arr: &Vec<i32>) -> i32 {
    let mut max_sum = arr[0];
    let mut current_sum = arr[0];
    for &num in &arr[1..] {
        current_sum = std::cmp::max(num, current_sum + num);
        max_sum = std::cmp::max(max_sum, current_sum);
    }
    max_sum
}

fn main() {
    let arr = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("Maximum Subarray Sum: {}", max_subarray_sum(&arr));
}

fun maxSubarraySum(arr: IntArray): Int {
    var maxSum = arr[0]
    var currentSum = arr[0]
    for (i in 1 until arr.size) {
        currentSum = maxOf(arr[i], currentSum + arr[i])
        maxSum = maxOf(maxSum, currentSum)
    }
    return maxSum
}

fun main() {
    val arr = intArrayOf(-2, 1, -3, 4, -1, 2, 1, -5, 4)
    println("Maximum Subarray Sum: ${maxSubarraySum(arr)}")
}

func maxSubarraySum(_ arr: [Int]) -> Int {
    var maxSum = arr[0]
    var currentSum = arr[0]
    for i in 1..<arr.count {
        currentSum = max(arr[i], currentSum + arr[i])
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", maxSubarraySum(arr))

function maxSubarraySum(arr: number[]): number {
    let maxSum = arr[0];
    let currentSum = arr[0];
    for (let i = 1; i < arr.length; i++) {
        currentSum = Math.max(arr[i], currentSum + arr[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

const arr: number[] = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("Maximum Subarray Sum:", maxSubarraySum(arr));

Time complexity

Space complexity

O(1)

Kadane's Algorithm uses only constant space with a few variables (max_sum and current_sum) to track the state—no extra arrays or recursion are used.