loading...
Cover image for Kadane's Algorithm & The Maximum Subarray Problem

Kadane's Algorithm & The Maximum Subarray Problem

alisabaj profile image Alisa Bajramovic Updated on ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

A common interview question is -- given an array of integers, return the maximum sum of a subarray of the array. A 'subarray' is contiguous, and can include just one integer, or all of them. In this problem, you can assume that the array contains negative numbers--otherwise, the maximum subarray would just be the entire array. (You can find the Leetcode question here.)

For example, let's say you were given the input array of [2, 1, -2, 3, 2]. Subarrays include [2], [2, 1], [2, 1, -2], and so on. Just by looking at this array, you may be tempted to say that the maximum subarray sum is 5, taken by adding the last two elements. However, the maximum subarray is the entire array, which sums to equal 6.

A brute-force solution to this problem would be to compile every single subarray of an input, sum its elements, and return the highest number. That approach would take O(n^2) time--typically a sign that a more efficient method is possible.

In this blog post, I'll be walking through a solution to this problem that uses Kadane's Algorithm, and solves this problem in O(n) time. This post is based on a video made by CS Dojo here, and I definitely encourage people to check it out.

Kadane's Algorithm

In this approach, you're checking what the maximum subarray at each element is. Kadane's Algorithm says that the maximum subarray at each element is either the current element itself, or the current element plus the maximum subarray ending at the previous element.

Let's see how this would look on the example input. We can first start by initializing the current maximum to equal the first element, since there are no prior maximums to compare it against. We'll also initialize the global maximum to equal the first element for the same reason. So, the current maximum is 2, and the global maximum is 2.

Checking the first element, 2, and setting it equal to the current and global max

Then, let's move on and check each next element, 1. According to Kadane, the largest sum is either the current element, or the sum of the current element and the previous largest sum. In this case, we're comparing 1, the current element, with 1+2, the sum of the current element and the previous largest sum. 3 is larger, so the current maximum becomes 3. Now, we have to check if the current maximum is greater than the previous maximum subarray, and if so, the current maximum becomes the global maximum. 3 is greater than 2, so 3 becomes the global maximum as well.

Checking the second element, 1, and finding the current and global max

We then do that again for -2. When comparing -2 with 3 + (-2), we get that 1 is larger, so that becomes the current maximum. Because 1 is not larger than the global maximum, the global maximum remains unchanged.

Checking the third element, -2, and findign the current and global max

Now we're onto element 3. The current maximum is either 3 or 3 + the previous current maximum, which is 1. That makes 4 the current maximum, and since 4 is greater than the existing global maximum, it's the new global maximum.

Checking the fourth element, 3, and finding the current and global max

Finally, we're at the last element, 2. Kadane's Algorithm says that the maximum is either the element itself, or the element plus the previous current maximum (this shows why thinking [3,2] is the maximum subarray is not the right answer, as you may have thought by quickly looking at the array). In this case, we're comparing if 2 is greater than 2 + 4, or 6. 6 is greater, so that becomes the new current maximum. 6 is also greater than the previous global maximum, so it's the global maximum as well.

Checking the final element, 2, and calculating the current and global max

There are no more elements to check, so this algorithm would return 6 as the global maximum.

Kadane's Algorithm in JavaScript

To write this algorithm out, we need to store a couple of variables that hold current and global maximum. We also need to walk through through the array and perform checks on each element. Finally, we'll return the global maximum.

Let's start by initializing the current max and the global max, setting it equal to the first element in the input array. We do this because the first element has no prior elements to check against.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  //...
}

Next, starting with the element at index 1, and looping through the end of the input array, we'll perform checks on each element. To do this, we'll use a for loop.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    //...
  }
  //...
}

Now, we want to see whether the current element, nums[i] is greater than the sum of the current element and the sum of the previous subarray, maxCurrent + nums[i]. This is a good place to use Math.max(), which will return the larger of the values. Whichever one is larger will become the new maxCurrent.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    //...
  }
  //...
}

Now that we have the maximum subarray ending at the current element, we have to check if it's larger than the global max. If it is, it'll be the new global max.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  //...
}

Once the for loop is finished, and all of the elements have been checked, we can return the global max.

function maxSubArray(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];
  for (let i = 1; i < nums.length; i++) {
    maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
    if (maxCurrent > maxGlobal) {
      maxGlobal = maxCurrent;
    }
  }
  return maxGlobal
}

And that's it! Let me know in the comments if you have any questions, or other approaches to this problem that you like.

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

I had a slight modification in this logic.
We can do without maxCurrent, coz if we encounter a -ve number it will always reduce the maxCurrent and a positive number will always increase it...
So we just keep modifying the current array with sum of all past elements as long as they are +ve... and not if -ve.
then we keep comparing maxGlobal with this sum.

var maxSubArray = function(nums) {
    if (nums.length == 0) 
        return 0;
    let max = nums[0];
    for (let i=1; i<nums.length; i++) {
        if (nums[i-1] > 0){
            nums[i] += nums[i-1];
        } 
        max = Math.max(nums[i], max);
    }
    return max;
};