Introduction

Kadane's algorithm is famous for returning the maximum subarray sum in linear time, but many real problems need more than the sum. If you want the actual subarray, the missing ingredient is to track where the current candidate segment started and when it becomes the new global best.

The Standard Kadane Idea

At each position, Kadane's algorithm decides between two choices:

• extend the current subarray
• start a new subarray at the current element

That gives the familiar recurrence:

• 'current = max(nums[i], current + nums[i])'
• 'best = max(best, current)'

To return the subarray itself, you keep the same logic and add index bookkeeping.

Track a Temporary Start Index

The key is to remember where the current candidate segment began.

If starting fresh at nums[i] is better than extending the previous sum, then the current subarray now begins at i. If the current running sum later becomes the best sum seen so far, promote that temporary start index into the final answer.

Python Implementation Returning the Subarray

1from typing import List, Tuple
2
3
4def kadane_with_subarray(nums: List[int]) -> Tuple[int, int, int, List[int]]:
5    if not nums:
6        raise ValueError("input must not be empty")
7
8    best_sum = nums[0]
9    current_sum = nums[0]
10
11    best_start = best_end = 0
12    temp_start = 0
13
14    for i in range(1, len(nums)):
15        if nums[i] > current_sum + nums[i]:
16            current_sum = nums[i]
17            temp_start = i
18        else:
19            current_sum += nums[i]
20
21        if current_sum > best_sum:
22            best_sum = current_sum
23            best_start = temp_start
24            best_end = i
25
26    return best_sum, best_start, best_end, nums[best_start:best_end + 1]
27
28
29arr = [4, -1, 2, 1, -5, 4]
30print(kadane_with_subarray(arr))

This returns the maximum sum, the start index, the end index, and the subarray itself.

Why This Works

temp_start marks the beginning of the current running candidate. When nums[i] alone is better than current_sum + nums[i], the old segment is no longer worth extending, so the candidate restarts at i.

Later, if the candidate becomes the best sum overall, the current candidate boundaries become the global answer.

That is the whole extension. Kadane's algorithm already knew which sum was best; now you also know where that sum came from.

All-Negative Arrays Need Care

A common incorrect implementation initializes sums to 0. That breaks cases such as [-5, -2, -7] because the real maximum subarray is [-2], not an empty sum of zero.

Correct initialization starts from the first element:

print(kadane_with_subarray([-5, -2, -7]))

That correctly identifies -2 and its one-element subarray.

Java Version

The same logic translates directly to Java.

1import java.util.Arrays;
2
3public class KadaneExample {
4    static class Result {
5        int maxSum;
6        int start;
7        int end;
8
9        Result(int maxSum, int start, int end) {
10            this.maxSum = maxSum;
11            this.start = start;
12            this.end = end;
13        }
14    }
15
16    static Result kadane(int[] nums) {
17        if (nums.length == 0) throw new IllegalArgumentException("empty array");
18
19        int bestSum = nums[0];
20        int currentSum = nums[0];
21        int bestStart = 0, bestEnd = 0, tempStart = 0;
22
23        for (int i = 1; i < nums.length; i++) {
24            if (nums[i] > currentSum + nums[i]) {
25                currentSum = nums[i];
26                tempStart = i;
27            } else {
28                currentSum += nums[i];
29            }
30
31            if (currentSum > bestSum) {
32                bestSum = currentSum;
33                bestStart = tempStart;
34                bestEnd = i;
35            }
36        }
37
38        return new Result(bestSum, bestStart, bestEnd);
39    }
40
41    public static void main(String[] args) {
42        int[] arr = {4, -1, 2, 1, -5, 4};
43        Result r = kadane(arr);
44        System.out.println(r.maxSum + " " + r.start + " " + r.end);
45        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, r.start, r.end + 1)));
46    }
47}

Complexity Stays the Same

Adding index tracking does not change the asymptotic performance.

• time complexity stays O(n)
• extra working space stays O(1)

The only extra cost is storing a few integers for boundaries.

Common Pitfalls

The biggest mistake is initializing sums to zero, which breaks all-negative inputs.

Another common issue is computing the correct maximum sum but forgetting to update the start and end indices at the right time.

Developers also sometimes mix inclusive and exclusive index conventions, especially when returning slices in languages that use exclusive end indices.

Finally, do not confuse Kadane's algorithm with non-contiguous subsequence problems. Kadane is specifically for contiguous subarrays.

Summary

• Kadane's algorithm can return the actual maximum subarray, not just its sum.
• Track a temporary start index for the current running segment.
• When the running segment becomes globally best, save its boundaries.
• Initialize from the first element so all-negative arrays work correctly.
• The algorithm still runs in linear time with constant extra working space.