Kadane Algorithm
Negative Numbers
Maximum Subarray Problem
Dynamic Programming
Algorithm Optimization

Kadane Algorithm Negative Numbers

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

In the world of computer science and programming, efficiently maximizing subarray sums is a frequent challenge, often addressed using the Kadane's Algorithm. While it is traditionally introduced in the context of arrays containing both positive and negative numbers, its behavior with arrays filled purely with negative numbers warrants a closer look. Here, we explore the intricacies of how Kadane's Algorithm handles scenarios dominated by negative numbers.

Understanding Kadane's Algorithm

Kadane's Algorithm is a brilliant example of dynamic programming aimed at finding the maximum sum subarray within a given one-dimensional numeric array. The elegance of this algorithm lies in its linear O(n) time complexity, making it feasible for large datasets.

The Algorithm

Here's a step-by-step explanation of Kadane’s Algorithm:

  1. Initialization: Start by initializing two variables:
    • `max_current` which keeps track of the maximum sum of the subarray ending at the current position.
    • `max_global` which keeps track of the overall maximum sum encountered so far.
  2. Iteration: Traverse through each element of the array:
    • For each element `A[i]`, update the `max_current` as the maximum of `A[i]` alone or `A[i]` plus the current subarray sum (`max_current` + `A[i]`).
    • If `max_current` is greater than `max_global`, update `max_global`.
  3. Result: After completing the iteration, `max_global` will contain the maximum sum.

Pseudocode

Below is the pseudocode for Kadane's Algorithm:

  • Initialize: `max_current = -5`, `max_global = -5`
  • Step through the array:
    • For `A[1] = -3`:
      • `max_current` becomes `max(-3, -5 + (-3)) = -3`
      • Update `max_global`: `max_global = max(-3, -5) = -3`
    • For `A[2] = -4`:
      • `max_current` becomes `max(-4, -3 + (-4)) = -4`
      • `max_global` stays at `-3`
    • For `A[3] = -2`:
      • `max_current` becomes `max(-2, -4 + (-2)) = -2`
      • Update `max_global`: `max_global = max(-2, -3) = -2`
    • For `A[4] = -7`:
      • `max_current` becomes `max(-7, -2 + (-7)) = -7`
      • `max_global` stays at `-2`
  • Result: The maximum sum subarray is `-2`.
  • In an array of negative numbers, the least negative number is the maximum sum.
  • Even though every subarray sum is negative, Kadane's algorithm efficiently navigates to identify the "largest" subarray sum.

Course illustration
Course illustration

All Rights Reserved.