Data Structures and Algorithms

Kadanes Algorithm

11 months, 4 weeks ago ; F(visit_count) + Value(1) views
Share this

Let's break down the problem, the approach taken, and perform a time and space complexity analysis for Kadane's Algorithm.


Problem

The problem we are trying to solve is to find the maximum sum of a contiguous subarray within a given one-dimensional array of integers.

 

# O(n) time | O(1) space
def kadanes_algorithm(array):
    """
    Find the maximum sum of a contiguous subarray within a one-dimensional array.

    Kadane's algorithm iterates through the array, keeping track of the maximum sum of
    subarrays ending at each index and the maximum sum encountered so far.

    Args:
        array (list of int): The input array.

    Returns:
        int: The maximum sum of a contiguous subarray within the input array.

    Example:
        >>> kadanes_algorithm([-2, 1, -3, 4, -1, 2, 1, -5, 4])
        6

    """
    # base case
    if len(array) <= 0:
		return 0

    # Initialize variables to store the maximum sum of subarrays ending at the current index
    # and the maximum sum encountered so far.
    max_sum_ending_here = array[0]
    max_sum_so_far = array[0]

    # Iterate through the array starting from the second element.
    for num in array[1:]:
        # Calculate the maximum sum of subarrays ending at the current index.
        # It can be either the current number or the sum of the previous subarray
        # ending at the previous index plus the current number.
        max_sum_ending_here = max(num, max_sum_ending_here + num)
        
        # Update the maximum sum encountered so far if the current sum is greater.
        max_sum_so_far = max(max_sum_so_far, max_sum_ending_here)
    
    # Return the maximum sum encountered during the iteration.
    return max_sum_so_far

print(f"kadanes_algorithm:: {kadanes_algorithm([3, 5, -9, 1,3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4])}")

Approach

Kadane's Algorithm provides an efficient solution to this problem. It iterates through the array, maintaining two variables:

  •     max_sum_ending_here: Represents the maximum sum of subarrays ending at the current index.
  •     max_sum_so_far: Represents the maximum sum encountered so far during the iteration.

At each index i, max_sum_ending_here is updated based on whether it is better to start a new subarray at index i or to extend the previous subarray ending at index i-1.

Similarly, max_sum_so_far is updated to keep track of the overall maximum sum encountered.


Time Complexity

  •     The algorithm iterates through the array once, visiting each element exactly once.
  •     At each iteration, constant-time operations are performed to update max_sum_ending_here and max_sum_so_far.
  •     Therefore, the time complexity of Kadane's Algorithm is O(n), where n is the length of the input array.

Space Complexity

  •     The algorithm uses only a constant amount of extra space, regardless of the size of the input array.
  •     It maintains only two variables (max_sum_ending_here and max_sum_so_far) throughout the iteration.
  •     Thus, the space complexity of Kadane's Algorithm is O(1).

Unit Tests

Below are some unit tests using Python's unittest module to test the robustness of Kadane's Algorithm:

import unittest


class TestKadanesAlgorithm(unittest.TestCase):
    def test_example_1(self):
        # Test the example given in the docstring
        self.assertEqual(kadanes_algorithm([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
    
    def test_empty_array(self):
        # Test with an empty array
        self.assertEqual(kadanes_algorithm([]), 0)
    
    def test_single_element(self):
        # Test with an array containing a single element
        self.assertEqual(kadanes_algorithm([5]), 5)
    
    def test_all_negative_elements(self):
        # Test with an array containing all negative elements
        self.assertEqual(kadanes_algorithm([-2, -3, -1, -5, -4]), -1)
    
    def test_all_positive_elements(self):
        # Test with an array containing all positive elements
        self.assertEqual(kadanes_algorithm([2, 3, 1, 5, 4]), 15)
    
    def test_mixed_elements(self):
        # Test with an array containing both positive and negative elements
        self.assertEqual(kadanes_algorithm([2, -3, 5, -1, 6, -7, 8]), 11)
    
    def test_all_zero_elements(self):
        # Test with an array containing all zero elements
        self.assertEqual(kadanes_algorithm([0, 0, 0, 0, 0]), 0)


if __name__ == '__main__':
    unittest.main()

These unit tests cover various scenarios:

  •     Testing with the example given in the docstring.
  •     Testing with an empty array.
  •     Testing with an array containing a single element.
  •     Testing with an array containing all negative elements.
  •     Testing with an array containing all positive elements.
  •     Testing with an array containing both positive and negative elements.
  •     Testing with an array containing all zero elements.

Each test case asserts whether the kadanes_algorithm() function returns the expected result for a given input.

These tests help ensure the correctness and robustness of Kadane's Algorithm.

Become a member
Get the latest news right in your inbox. We never spam!

Read next

How to Check If Two Words Are Anagrams in Python

How to Check if Two Words are Anagrams in Python Clarity and precision are essential in sol… Read More

3 days, 8 hours ago . 256 views