Kadane's Algorithm: Maximum Subarray Sum (Finding and Printing)

A fundamental problem in Array Data Structures and Algorithms is finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum. This note covers the entire progression from the initial $O(N^3)$ Brute Force method, to an optimized $O(N^2)$ approach, and finally to the optimal $O(N)$ solution using Kadane's Algorithm, including how to track and print the actual subarray yielding the maximum sum.

1. Problem Definition & Core Concepts

The goal is to identify a contiguous segment of an array such that the sum of its elements is maximized, and return that maximum sum.

What is a Subarray?

A subarray is defined as a continuous, uninterrupted part of an array.

• Contiguous: Elements must appear sequentially without skipping any middle elements.
• Single Element: A single element is a valid subarray of length 1.
• Entire Array: The complete array is also a valid subarray.

Array: [-2, -3, 4, -1, -2, 1, 5, -3]

Valid Subarray:     [-3, 4, -1]       (Elements are contiguous)
Invalid Subarray:   [-2, 4, 5]        (Elements skip -3, -1, -2; this is a Subsequence)

Note: Subarray vs. Subsequence

• Subarray: Elements must be strictly contiguous.
• Subsequence: Elements maintain their original relative order but do not need to be contiguous.

2. Naive Brute Force Approach ($O(N^3)$)

To guarantee finding the maximum sum, the most straightforward approach is to evaluate every possible subarray, compute each of their sums, and keep track of the maximum value encountered.

Mechanics of Generating All Subarrays

1. Outer loop (i) marks the starting index of the subarray.
2. Inner loop (j) marks the ending index of the subarray.
3. Innermost loop (k) iterates from i to j to compute the sum of elements within that range.

Code Implementation (C++)

#include <vector>
#include <climits>
#include <algorithm>

int maxSubarraySumBruteForce(const std::vector<int>& arr) {
    int n = arr.size();
    int maxi = INT_MIN;

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += arr[k];
            }
            maxi = std::max(maxi, sum);
        }
    }
    return maxi;
}

Complexity

• Time Complexity: $O(N^3)$ — Generating all pairs $(i, j)$ takes $O(N^2)$, and summing elements from $i$ to $j$ takes up to $O(N)$ steps.
• Space Complexity: $O(1)$ — Only auxiliary variables (sum, maxi) are used.

3. Better Approach ($O(N^2)$)

We can optimize the $O(N^3)$ approach by observing that the sum of the subarray spanning from index i to j is simply the sum of the subarray from i to j - 1 plus arr[j].

There is no need to re-sum all elements from i to j using a third loop. Instead, as the pointer j moves forward, add the current element arr[j] directly to an ongoing running sum.

Visual Workflow

Code Implementation (C++)

#include <vector>
#include <climits>
#include <algorithm>

int maxSubarraySumBetter(const std::vector<int>& arr) {
    int n = arr.size();
    int maxi = INT_MIN;

    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j]; // Reuse the sum from previous iterations
            maxi = std::max(maxi, sum);
        }
    }
    return maxi;
}

Complexity

• Time Complexity: $O(N^2)$ — Two nested loops iterate through all starting and ending index combinations.
• Space Complexity: $O(1)$ — No extra data structures required.

4. Optimal Approach: Kadane's Algorithm ($O(N)$)

While $O(N^2)$ is better than cubic time, an interviewer will expect a linear-time $O(N)$ solution. This is achieved using Kadane's Algorithm.

Core Intuition & Mental Model

Why carry forward a subarray sum if it becomes negative?

• A negative running sum will only decrease or hamper the sum of any future contiguous subarray that extends from it.
• If your accumulated sum drops below 0, it is optimal to reset the sum to 0. This effectively abandons the current negative prefix and marks the potential start of a new subarray at the next element.

Key Decision Rubric

1. Accumulate: Add the current element arr[i] to sum.
2. Evaluate Maximum: Update max_sum if sum > max_sum.
3. Reset Condition: If sum < 0, reset sum = 0. Carrying a negative prefix into subsequent elements will only reduce their combined value.

5. Dry Run Walkthrough of Kadane's Algorithm

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

Initial State: sum = 0, max_sum = LONG_MIN

Final Maximum Subarray Sum: 7 (corresponding to the subarray [4, -1, -2, 1, 5]).

6. Edge Cases & Special Considerations

1. All Negative Numbers

If the array contains only negative numbers (e.g., [-4, -2, -3, -1]):

• Standard Kadane's will compare elements to max_sum (updating it to -1, the largest single element), and then reset sum to 0 whenever it becomes negative.
• Result: max_sum = -1.

2. Variation: Empty Subarray Allowed

Some problem formulations state: "If no subarray yields a positive sum, you can choose an empty subarray with sum 0."

• In this variation, if max_sum < 0 at the end of execution, explicitly update max_sum = 0.

if (maxi < 0) {
    maxi = 0;
}

7. Implementation of Kadane's Algorithm

C++ Code

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

long long maxSubarraySum(const std::vector<int>& arr) {
    long long maxi = LONG_MIN;
    long long sum = 0;

    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];

        if (sum > maxi) {
            maxi = sum;
        }

        // If sum drops below 0, discard the current running sub-array
        if (sum < 0) {
            sum = 0;
        }
    }

    // Optional condition if empty subarray (sum = 0) is allowed:
    // if (maxi < 0) maxi = 0;

    return maxi;
}

Java Code

public class KadaneAlgorithm {
    public static long maxSubarraySum(int[] arr) {
        long maxi = Long.MIN_VALUE;
        long sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (sum > maxi) {
                maxi = sum;
            }

            if (sum < 0) {
                sum = 0;
            }
        }

        return maxi;
    }
}

Python Code

import sys

def max_subarray_sum(arr: list[int]) -> int:
    maxi = -sys.maxsize - 1
    running_sum = 0

    for num in arr:
        running_sum += num

        if running_sum > maxi:
            maxi = running_sum

        if running_sum < 0:
            running_sum = 0

    return maxi

8. Follow-up: Finding and Printing the Maximum Subarray

A common interview follow-up is: "Don't just return the maximum sum—print the actual subarray that produces this sum."

Tracking Mechanics

To track the subarray bounds:

1. Maintain a start variable that records where a new potential subarray begins.
2. Whenever sum == 0, set start = i (the index of the next potential starting element).
3. Whenever sum > maxi updates the maximum sum, record the exact bounds:
   • ansStart = start
   • ansEnd = i

9. Complete Code Walkthrough: Subarray Tracking Implementation

C++ Source Code

#include <iostream>
#include <vector>
#include <climits>

void printAndReturnMaxSubarray(const std::vector<int>& arr) {
    long long maxi = LONG_MIN;
    long long sum = 0;

    int start = 0;
    int ansStart = -1;
    int ansEnd = -1;

    for (int i = 0; i < arr.size(); i++) {
        // If sum is 0, we are starting a fresh subarray sequence
        if (sum == 0) {
            start = i;
        }

        sum += arr[i];

        // Found a new maximum sum, update recording indices
        if (sum > maxi) {
            maxi = sum;
            ansStart = start;
            ansEnd = i;
        }

        // Reset negative sums
        if (sum < 0) {
            sum = 0;
        }
    }

    std::cout << "Maximum Subarray Sum: " << maxi << std::endl;
    std::cout << "The Subarray is: [ ";
    for (int i = ansStart; i <= ansEnd; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << "]" << std::endl;
}

int main() {
    std::vector<int> arr = {-2, -3, 4, -1, -2, 1, 5, -3};
    printAndReturnMaxSubarray(arr);
    return 0;
}

Execution Trace Output

Maximum Subarray Sum: 7
The Subarray is: [ 4 -1 -2 1 5 ]

10. Complexity Analysis & Comparison

Summary and Key Takeaways

• Contiguous Constraint: A subarray must be contiguous; skipping elements forms a subsequence, not a subarray.
• Core Kadane Philosophy: Discard running sums that drop below zero (sum < 0 => sum = 0). A negative prefix will always decrease the sum of any subsequent elements.
• Single-Pass Optimization: Kadane's algorithm reduces the problem complexity from $O(N^2)$ to $O(N)$ time with $O(1)$ auxiliary space.
• Tracking Subarray Indices:
  • Set start = i whenever sum == 0.
  • Capture ansStart = start and ansEnd = i whenever sum > maxi.
• Edge Case Awareness:
  • For arrays with all negative numbers, standard Kadane's returns the maximum single element (least negative).
  • If the problem permits empty subarrays, cap the final output at 0 if maxi < 0.