Maximum Subarray (Kadane's)

Welcome back to CodeYourCraft! Today, we're diving into a fascinating algorithm known as Kadane's Algorithm, which helps us find the maximum sum subarray within an array of numbers. This algorithm is crucial for beginners and intermediates alike, and it's used in various real-world applications.

📝 Note: This lesson is designed to be easy to understand, so we'll start from the basics and gradually move towards more complex concepts.

What is a Subarray?

Before diving into Kadane's Algorithm, let's define what we mean by a subarray. A subarray is simply a contiguous part of an array. For example, if we have the array [1, 2, 3, 4, -5, 6], the subarrays are:

[1]
[2]
[3]
[4]
[-5]
[6]
[1, 2]
[2, 3]
[3, 4]
[4, -5]
[-5, 6]
[1, 2, 3]
[2, 3, 4]
[3, 4, -5]
[4, -5, 6]
[1, 2, 3, 4]
[2, 3, 4, -5]
[3, 4, -5, 6]
[1, 2, 3, 4, -5]
[2, 3, 4, -5, 6]
[1, 2, 3, 4, -5, 6]

💡 Pro Tip: In this lesson, we'll be focusing on finding the maximum sum subarray, not the maximum sum contiguous sequence, which may contain negative numbers.

Kadane's Algorithm Explained

Kadane's Algorithm works by maintaining two variables: currentMax and globalMax.

currentMax keeps track of the maximum sum subarray encountered so far within the current subarray we're considering.
globalMax stores the maximum sum subarray found across the entire array.

At the end of the algorithm, globalMax will hold the maximum sum subarray in the input array.

Let's walk through an example to better understand how Kadane's Algorithm works:

python

arr = [-2, -3, 4, -1, -2, 1, 5, -3]
currentMax = globalMax = arr[0]

for num in arr:
    if currentMax > 0:
        currentMax += num
    else:
        currentMax = num

    if currentMax > globalMax:
        globalMax = currentMax

In this example, we start with currentMax and globalMax both initialized to the first element in the array, -2. We then loop through the rest of the array, updating currentMax and globalMax as needed.

Here's what happens at each step:

currentMax starts at -2 (the first element in the array)
We encounter -3. Since currentMax is negative, we update it to -3. globalMax remains -2.
We encounter 4. Now currentMax is updated to 1 (-3 + 4). globalMax is updated to 1 (1 > -2) since it's the new maximum we've found so far.
We encounter -1. Since currentMax is positive, we update it to 0 (1 - 1). globalMax remains 1.
We encounter -2. Since currentMax is negative, we update it to -2. globalMax remains 1.
We encounter 1. Now currentMax is updated to 1 (-2 + 1). Since it's still the same as globalMax, we don't update it.
We encounter 5. Now currentMax is updated to 6 (1 + 5). globalMax is updated to 6 since it's the new maximum we've found so far.
We encounter -3. Since currentMax is positive, we update it to -3. globalMax remains 6.

By the end of the algorithm, globalMax will be 6, which is the maximum sum subarray in the input array [-2, -3, 4, -1, -2, 1, 5, -3].

Implementing Kadane's Algorithm

Now that we've gone through the explanation, let's implement Kadane's Algorithm in Python.

python

def max_subarray_sum(arr):
    if not arr:
        return None

    current_max = global_max = arr[0]

    for num in arr[1:]:
        if current_max > 0:
            current_max += num
        else:
            current_max = num

        if current_max > global_max:
            global_max = current_max

    return global_max

arr = [-2, -3, 4, -1, -2, 1, 5, -3]
print(max_subarray_sum(arr))  # Output: 6

💡 Pro Tip: You can use the max() function along with the sum() function to find the maximum sum subarray in a more Pythonic way:

python

def max_subarray_sum(arr):
    if not arr:
        return None

    current_max = global_max = max(arr)

    for num in arr:
        current_max = max(num, current_max + num)
        if current_max > global_max:
            global_max = current_max

    return global_max

Both implementations give the same result for the input array [-2, -3, 4, -1, -2, 1, 5, -3].

Quiz

That's all for today! With Kadane's Algorithm, you now have a powerful tool to find the maximum sum subarray in an array. This algorithm is a fundamental concept in the world of data structures and algorithms, and mastering it will help you grow as a developer.

Stay tuned for more exciting lessons here at CodeYourCraft! 🚀