Kadane’s Algorithm: Efficiently Finding the Maximum Subarray Sum

The challenge of locating the contiguous subarray within a one-dimensional array of numbers that has the largest sum is a classic problem in computer science. While seemingly simple, brute-force approaches can be inefficient for larger datasets. This is where Kadane’s Algorithm shines, providing an optimal and elegant solution.

Understanding the Problem

Imagine you have an array of integers, which can include both positive and negative numbers. Your goal is to identify a sequence of adjacent numbers within this array whose sum is greater than any other contiguous sequence. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] yields a sum of 6, which is the maximum possible.

How Kadane’s Algorithm Works

Kadane’s Algorithm is a dynamic programming approach that processes the array from left to right, maintaining two crucial values:

1. currentMax: This tracks the maximum sum of a subarray ending at the current position.
2. globalMax: This keeps track of the overall maximum sum found across all subarrays encountered so far.

The core idea is that for each element in the array, we decide whether to extend the current subarray (by adding the element to currentMax) or to start a new subarray from the current element itself (if the current element is greater than currentMax + currentElement). The globalMax is updated whenever currentMax surpasses it.

Algorithm Steps:

1. Initialize globalMax and currentMax to the first element of the array.
2. Iterate through the array starting from the second element.
3. For each element num:
   • Update currentMax to be the maximum of:
     • num (starting a new subarray from this element)
     • currentMax + num (extending the current subarray)
   • Update globalMax to be the maximum of:
     • globalMax (the previously recorded maximum)
     • currentMax (the maximum sum ending at the current position)
4. After iterating through all elements, globalMax will hold the maximum contiguous subarray sum.

JavaScript Implementation

Here’s a straightforward implementation of Kadane’s Algorithm in JavaScript:

/**
 * Finds the maximum sum of a contiguous subarray using Kadane's Algorithm.
 * @param {number[]} nums - The input array of numbers.
 * @returns {number} The maximum sum found.
 */
const maxSubarraySum = function(nums) {
    if (nums.length === 0) {
        return 0; // Or handle as an error, depending on requirements
    }

    let globalMax = nums[0]; // Overall maximum sum found so far
    let currentMax = nums[0]; // Maximum sum ending at the current position

    for (let i = 1; i < nums.length; i++) {
        // Option 1: Extend the current subarray by adding nums[i]
        // Option 2: Start a new subarray from nums[i]
        currentMax = Math.max(nums[i], currentMax + nums[i]);

        // Update the overall maximum sum if currentMax is greater
        globalMax = Math.max(globalMax, currentMax);
    }

    return globalMax;
};

Step-by-Step Example Walkthrough

Let’s trace the algorithm with the example array: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Initialization:
globalMax = -2
currentMax = -2

Iteration:

• i = 1 (num = 1):
  • currentMax = Math.max(1, -2 + 1) = Math.max(1, -1) = 1
  • globalMax = Math.max(-2, 1) = 1
• i = 2 (num = -3):
  • currentMax = Math.max(-3, 1 + (-3)) = Math.max(-3, -2) = -2
  • globalMax = Math.max(1, -2) = 1
• i = 3 (num = 4):
  • currentMax = Math.max(4, -2 + 4) = Math.max(4, 2) = 4
  • globalMax = Math.max(1, 4) = 4
• i = 4 (num = -1):
  • currentMax = Math.max(-1, 4 + (-1)) = Math.max(-1, 3) = 3
  • globalMax = Math.max(4, 3) = 4
• i = 5 (num = 2):
  • currentMax = Math.max(2, 3 + 2) = Math.max(2, 5) = 5
  • globalMax = Math.max(4, 5) = 5
• i = 6 (num = 1):
  • currentMax = Math.max(1, 5 + 1) = Math.max(1, 6) = 6
  • globalMax = Math.max(5, 6) = 6
• i = 7 (num = -5):
  • currentMax = Math.max(-5, 6 + (-5)) = Math.max(-5, 1) = 1
  • globalMax = Math.max(6, 1) = 6
• i = 8 (num = 4):
  • currentMax = Math.max(4, 1 + 4) = Math.max(4, 5) = 5
  • globalMax = Math.max(6, 5) = 6

Final Result: After the loop completes, globalMax is 6.

Conclusion

Kadane’s Algorithm stands as an excellent example of how dynamic programming can solve complex problems with remarkable efficiency. Its time complexity is O(n), as it only requires a single pass through the array, making it highly suitable for large datasets. This algorithm is a fundamental concept for anyone delving into competitive programming or optimizing array manipulation tasks.