Kadanes Algorithm

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.