Kadane's Algorithm: Tracking Subarray Indices

Welcome back! In our last lesson, we solidified your understanding of Kadane's algorithm by translating its core logic into a robust implementation. We focused on finding the maximum subarray sum and correctly handling the important edge case of an all-negative array.

This lesson builds directly on that foundation to address a common and practical follow-up: finding the subarray itself. Your goal for this lesson is to learn how to adapt Kadane's algorithm to track the start and end indices of the maximum subarray. Knowing not just the "what" (the sum) but also the "where" (the indices) is a frequent requirement in real-world applications and coding challenges, from analyzing stock market trends to processing data streams.

The Logic: Augmenting Kadane's Algorithm

The beauty of Kadane's algorithm is its simplicity, and thankfully, we can preserve that while adding the logic to track indices. We'll need to introduce a few new variables to our existing implementation.

Recall the core of the algorithm from our previous lesson: we iterate through the array, maintaining a current_sum. If this current_sum becomes negative, we discard it and reset it to 0. This very action—discarding a useless prefix—gives us the crucial signal we need. It tells us that any potential new maximum subarray must start from the next element.

Here is the strategy we'll employ:

1. max_sum and current_sum: These behave exactly as before. max_sum tracks the best sum found so far, and current_sum tracks the sum of the subarray ending at the current position.
2. potential_start: We'll use a variable to keep track of the starting index of the current subarray candidate. When current_sum drops below zero and we reset it, it means the subarray we were tracking is no longer a candidate. We must therefore update potential_start to the next index (i + 1).
3. final_start and final_end: These variables will store the official start and end indices of the overall maximum subarray found so far. We only update these when we find a new max_sum—that is, when current_sum > max_sum. When this happens, final_end is simply the current index i, and final_start is the potential_start we've been tracking.

The take U forward channel provides an excellent visual walkthrough of this exact logic.

From Logic to Code

As you saw in the video, the modifications are quite small and fit neatly into the existing loop. Let's translate this into a Python implementation.

def max_subarray_with_indices(nums):
    if not nums:
        return 0, -1, -1 # Or some other indication of an empty array

    max_so_far = float('-inf')
    current_sum = 0
    
    start_index = 0
    end_index = -1
    potential_start = 0

    for i, num in enumerate(nums):
        current_sum += num

        if current_sum > max_so_far:
            max_so_far = current_sum
            start_index = potential_start
            end_index = i

        if current_sum < 0:
            current_sum = 0
            potential_start = i + 1
            
    # Handle the all-negative case separately
    # If max_so_far is still negative, it means we never had a positive current_sum.
    # The true max is a single element.
    if max_so_far < 0:
        max_so_far = float('-inf')
        for i, num in enumerate(nums):
            if num > max_so_far:
                max_so_far = num
                start_index = i
                end_index = i

    return max_so_far, start_index, end_index

# Example usage:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = max_subarray_with_indices(arr)
print(f"Max sum: {max_sum}, Subarray: {arr[start:end+1]}") 
# Output: Max sum: 6, Subarray: [4, -1, 2, 1]

arr_neg = [-5, -2, -3]
max_sum, start, end = max_subarray_with_indices(arr_neg)
print(f"Max sum: {max_sum}, Subarray: {arr_neg[start:end+1]}")
# Output: Max sum: -2, Subarray: [-2]

Notice the small complication for the all-negative case. Our simple logic relies on current_sum becoming positive at some point. If all numbers are negative, max_so_far will be updated correctly (as we saw in the previous lesson), but the indices might not be. The most straightforward way to handle this is to run the basic potential_start logic and then, if the final max_so_far is negative, we know the answer must be the single largest element. The code above shows one way to correct this.

A slightly cleaner approach integrates this logic directly, as shown in the following resource.

Walkthrough: A Step-by-Step Trace

Let's trace our algorithm with the array arr = [4, -1, 2, 1, -5, 4] to see the variables in action. We'll use a slightly more elegant implementation that correctly handles all-negative cases without a second pass.

The key is to initialize max_so_far with the first element and start the loop from there.

Let's use the other example arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

The final answer is max_sum = 6, starting at index 3 and ending at index 6.

Conclusion

You have now extended Kadane's algorithm to solve the complete version of the problem: finding not only the maximum sum but also the subarray that produces it. This is a powerful and efficient pattern to have in your toolkit.

Key Takeaways:

• The Signal: The moment Kadane's algorithm resets the current_sum to zero is the signal that a new potential subarray begins at the next index.
• Variable Augmentation: We can track indices by adding three variables: a potential_start that resets with current_sum, and a final_start and final_end that are updated only when a new max_so_far is discovered.
• Robustness: Handling the all-negative case requires a slight modification or a simple check to ensure the single largest element is returned correctly.

In our next lesson, we will explore how this powerful pattern can serve as a subroutine for solving more complex problems. Specifically, we will apply Kadane's algorithm to variants such as the maximum circular subarray sum, where the array can "wrap around."