How to find the maximum subarray sum using the greedy approach

Key takeaways:

• Kadane’s algorithm for maximum subarray sum: This problem is efficiently solved using Kadaness Algorithm with time complexity of $O(n)$, making it suitable for large input arrays.

• Dynamic subarray management: The algorithm dynamically keeps track of the maximum subarray sum as it iterates through the array, updating the result when a higher sum is found.

• Optimal for handling mixed positive and negative numbers: Kadane’s Algorithm is designed to handle arrays with both positive and negative numbers, ensuring the maximum sum subarray is identified even when negative values are present.

• Frequently asked in coding interviews: Problems involving finding the maximum subarray sum are common in technical interviews at top tech companies like Google, Microsoft, and Facebook.

• Real-world applications: This algorithm has applications in areas like stock market analysis, weather prediction, and any scenario where finding the maximum sum of consecutive elements is important.

• Algorithmic efficiency: Kadane’s Algorithm is an optimal, linear-time solution, demonstrating the importance of efficiency in solving real-world problems.

What is a maximum subarray sum?

The maximum subarray sum is the largest possible sum of a contiguous subarray within a given array. The subarray can consist of any number of consecutive elements, and the goal is to find the subarray that yields the highest sum.

Problem statement

Given an array of integers, nums, find the sum of a subarraya contiguous subset of an array that contains at least one element and has the greatest sum of all the subarrays.

Let’s understand this with the help of an example array [-3, 1, -2, 5, 0, 3, 2, -4, 6]. Out of all the possible subarrays, the subarray, [5, 0, 3, 2, -4, 6], produces a maximum sum of 12, so the output of this input will be 12.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

Example

Knowledge test

Let’s take a moment to ensure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem.

The solution to the maximum subarray sum problem

The maximum subarray sum problem can be efficiently solved using Kadane’s algorithm, a greedy approach that simplifies the decision-making process for finding the maximum sum of a contiguous subarray. The idea behind this approach is to iteratively decide whether to continue adding the current element to the existing subarray or start a new subarray. This decision is based on whether the current sum would be better by adding the current element or resetting the sum to just the current element itself.

In Kadane’s algorithm, we maintain two variables: the current subarray sum and the global maximum sum encountered so far. Starting from the first element, we check if adding the current element to the existing sum will increase it. If adding it makes the sum smaller, we reset the current sum to just the current element, effectively starting a new subarray. We continuously update the global maximum sum if the current sum exceeds it.

Here’s the detailed algorithm for the approach we just discussed:

1. Initialization:

   1. We initialize a varaible curr_max to the first element of the array, representing the current subarray sum.

   2. We’ll also initalize global_max to point the first element, representing the highest subarray sum encountered so far.

2. Iterating through the array:

   1. We’ll traverse from the second element (index 1) and process each element:

      1. If curr_max becomes negative, we reset it to the current element, starting a new subarray.

      2. Otherwise, we add the current element to curr_max, extending the current subarray.

      3. After updating curr_max, we’ll compare it with global_max. If curr_max exceeds global_max, the global maximum is updated.

3. Return the result:

   1. Once the loop finishes, we return global_max, which holds the maximum sum of any contiguous subarray.

Let’s look at the illustration below to better understand the solution:

Let’s look at the Python code for this solution below:

Complexity analysis

Time complexity: Since we are only looping through the array once, the algorithm’s time complexity is $O(n)$, where n is the length of the array.

Space complexity: The space complexity of this algorithm is $O(1)$, as we don’t need any additional memory (other than variables to store currentSum and maximumSum).

Why does the greedy approach work?

1. The greedy strategy ensures that negative subarrays are ignored early, allowing the algorithm to focus on positive-sum subarrays.

2. The running total (currentSum) and a comparison with the global maximum (maximumSum) guarantee the largest sum is found.

Additional resources

To learn more about data structures and algorithms and practice more LeetCode-based problems. Look at the following list of curated courses at Educative:

• Coderust: Hacking the Coding Interview

• Data Structures for Coding Interviews in JavaScript

• Grokking the Coding Interview Patterns