Maximum Subarray Sum in Python and Java Using Kadane's Algorithm

Problem Statement

Given an integer array nums, find the subarray with the largest sum and return its sum.

Input:
nums = [-3, 8, -2, 5, -6, 10, -1]

Output:
15

The subarray [8, -2, 5, -6, 10] has the largest sum.

8 + (-2) + 5 + (-6) + 10 = 15

What Is a Subarray?

A subarray is a continuous part of an array. That means all elements must be next to each other. We cannot skip elements.

nums = [8, -2, 5, -6, 10]

Valid subarray:
[8, -2, 5]

Invalid subarray:
[8, 5, 10]

Why invalid?
Because -2 and -6 were skipped.

Simple Approach

The simple approach is to generate all possible subarrays and calculate their sums. Then we return the maximum sum.

This works, but it is not efficient for large arrays because there can be many subarrays.

• Brute force solution: O(n²)
• Optimized Kadane's Algorithm: O(n)
• Space complexity: O(1)

Main Idea of Kadane's Algorithm

Kadane's Algorithm uses one simple idea. At every index, we ask:

Should I continue the previous subarray?

OR

Should I start a new subarray from the current number?

If the previous sum is useful, we continue it. If the previous sum is harmful, we start fresh from the current number.

Important Variables

We use two variables:

current_sum = best subarray sum ending at the current index

max_sum = best maximum subarray sum found so far

For every number, we update these two values.

current_sum = max(current number, current_sum + current number)

max_sum = max(max_sum, current_sum)

Why This Works

If current_sum becomes negative, then adding it to the next number will only make the next sum smaller. So it is better to start a new subarray from the current number.

This is why Kadane's Algorithm can find the best answer without checking every possible subarray.

Example 1

Input:
nums = [-3, 8, -2, 5, -6, 10, -1]

Output:
15

Explanation:
The maximum sum subarray is [8, -2, 5, -6, 10].

8 + (-2) + 5 + (-6) + 10 = 15

Example 2

Input:
nums = [-5, -2, -8, -1, -4]

Output:
-1

Explanation:
All numbers are negative, so the best subarray is the single largest number.

The largest number is -1.

Watch the Video

Watch on YouTube: https://youtu.be/c9w3wT74oJ0

Step-by-Step Dry Run

Let's dry run this input:

nums = [-3, 8, -2, 5, -6, 10, -1]

At the beginning:

current_sum = -3
max_sum = -3

Now check each number:

num = 8
current_sum = max(8, -3 + 8) = 8
max_sum = max(-3, 8) = 8

num = -2
current_sum = max(-2, 8 + -2) = 6
max_sum = max(8, 6) = 8

num = 5
current_sum = max(5, 6 + 5) = 11
max_sum = max(8, 11) = 11

num = -6
current_sum = max(-6, 11 + -6) = 5
max_sum = max(11, 5) = 11

num = 10
current_sum = max(10, 5 + 10) = 15
max_sum = max(11, 15) = 15

num = -1
current_sum = max(-1, 15 + -1) = 14
max_sum = max(15, 14) = 15

Final answer = 15

Python Solution

This Python solution starts with the first element. Then it loops from the second element and updates current_sum and max_sum.

class MaximumSubarrayCalculator:
    def find_maximum_subarray_sum(self, numbers):
        current_sum = numbers[0]
        max_sum = numbers[0]

        for index in range(1, len(numbers)):
            current_number = numbers[index]

            current_sum = max(current_number, current_sum + current_number)
            max_sum = max(max_sum, current_sum)

        return max_sum


# Example usage
numbers1 = [-3, 8, -2, 5, -6, 10, -1]
numbers2 = [-5, -2, -8, -1, -4]

calculator = MaximumSubarrayCalculator()

print(calculator.find_maximum_subarray_sum(numbers1))  # Output: 15
print(calculator.find_maximum_subarray_sum(numbers2))  # Output: -1

Java Solution

The Java solution follows the same logic. We use currentSum to store the best sum ending at the current index, and maxSum to store the best answer found so far.

class MaximumSubarrayCalculator {
    public int findMaximumSubarraySum(int[] numbers) {
        int currentSum = numbers[0];
        int maxSum = numbers[0];

        for (int index = 1; index < numbers.length; index++) {
            int currentNumber = numbers[index];

            currentSum = Math.max(currentNumber, currentSum + currentNumber);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] numbers1 = {-3, 8, -2, 5, -6, 10, -1};
        int[] numbers2 = {-5, -2, -8, -1, -4};

        MaximumSubarrayCalculator calculator = new MaximumSubarrayCalculator();

        System.out.println(calculator.findMaximumSubarraySum(numbers1)); // Output: 15
        System.out.println(calculator.findMaximumSubarraySum(numbers2)); // Output: -1
    }
}

Code Explanation

Step 1: Start with the First Element

We set both current_sum and max_sum to the first element. This is important because the array may contain only negative numbers.

Step 2: Loop Through the Array

Starting from the second element, we check whether it is better to start a new subarray or continue the previous subarray.

Step 3: Update Current Sum

current_sum = max(current_number, current_sum + current_number)

This line chooses the better option between starting fresh and continuing the previous subarray.

Step 4: Update Maximum Sum

max_sum = max(max_sum, current_sum)

This line stores the best answer found so far.

Step 5: Return the Answer

After the loop ends, max_sum contains the largest subarray sum.

Output for the Examples

Example 1 Output:
15

Example 2 Output:
-1

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

The algorithm is fast because it visits each element only once. It also does not use any extra array.

Key Points to Remember

• A subarray must be continuous.
• Kadane's Algorithm solves the problem in one loop.
• current_sum stores the best sum ending at the current index.
• max_sum stores the best answer found so far.
• This solution works even when all numbers are negative.

Conclusion

The maximum subarray sum problem can be solved efficiently using Kadane's Algorithm. Instead of checking all possible subarrays, we make the best decision at every index.

This method is simple, fast, and commonly used in coding interviews. It works in O(n) time and uses only O(1) extra space.