Kadane’s Algorithm | Maximum Sum of Contiguous Subarray

Kadane’s Algorithm is a famous algorithm used for finding the maximum sum of a contiguous subarray within a one-dimensional numeric array. This problem is often referred to as the “Maximum Subarray Problem” and can be solved efficiently using Kadane’s Algorithm with a time complexity of O(n).

Table of Contents

Explanation

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

  1. Initialization:
    • Set two variables: max_so_far and max_ending_here.
    • Both variables are initialized to the first element of the array.
    • max_so_far keeps track of the maximum sum found so far.
    • max_ending_here keeps track of the maximum sum of the subarray ending at the current position.
  2. Iterate through the array:
    • Starting from the second element (index 1) to the end of the array, update max_ending_here to be the maximum of the current element itself or the current element added to max_ending_here.
    • Update max_so_far to be the maximum of max_so_far and max_ending_here.
  3. Return the result:
    • The value of max_so_far will be the maximum sum of the contiguous subarray.

Pseudocode for Kadane's Algorithm

				
					function kadane(array):
    max_so_far = array[0]
    max_ending_here = array[0]

    for i from 1 to length(array) - 1:
        max_ending_here = max(array[i], max_ending_here + array[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

				
			

Example

Kadane's Algorithm for Maximum Sum of Contiguous Subarray

Let's consider an example array: [ 3, -2, 5, -1, 6, -3, 2, 4, -5, 7, -6, 1, 4, -2, 3 ].

  1. Initialization:
    • max_so_far = 3
    • max_ending_here = 3
  2. Iterate through the array:
    • At index 1: max_ending_here = max(-2, 3 + (-2)) = 1 & max_so_far = max(3, 1) = 3
    • At index 2: max_ending_here = max(5, 1 + 5) = 6 & max_so_far = max(3, 6) = 6
    • At index 3: max_ending_here = max(-1, 6 + (-1)) = 5 & max_so_far = max(6, 5) = 6
    • At index 4: max_ending_here = max(6, 5 + 6) = 11 & max_so_far = max(6, 11) = 11
    • At index 5: max_ending_here = max(-3, 11 + (-3)) = 8 & max_so_far = max(11, 8) = 11
    • At index 6: max_ending_here = max(2, 8 + 2) = 10 & max_so_far = max(11, 10) = 11
    • At index 7: max_ending_here = max(4, 10 + 4) = 14 & max_so_far = max(11, 14) = 14
    • At index 8: max_ending_here = max(-5, 14 + (-5)) = 9 & max_so_far = max(14, 9) = 14
    • At index 9: max_ending_here = max(7, 9 + 7) = 16 & max_so_far = max(14, 16) = 16
    • At index 10: max_ending_here = max(-6, 16 + (-6)) = 10 & max_so_far = max(16, 10) = 16
    • At index 11: max_ending_here = max(1, 10 + 1) = 11 & max_so_far = max(16, 11) = 16
    • At index 12: max_ending_here = max(4, 11 + 4) = 15 & max_so_far = max(16, 15) = 16
    • At index 13: max_ending_here = max(-2, 15 + (-2)) = 13 & max_so_far = max(16, 13) = 16
    • At index 14: max_ending_here = max(3, 13 + 3) = 16 & max_so_far = max(16, 16) = 16
  3. The maximum sum of the contiguous subarray is 16, which occurs from indices 2 to 9 [ 5, -1, 6, -3, 2, 4, -5, 7 ].

Python Code Implementation

				
					def kadane(arr):
    max_so_far = arr[0]
    max_ending_here = arr[0]

    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

# Example usage
temperature_change = [3, -2, 5, -1, 6, -3, 2, 4, -5, 7, -6, 1, 4, -2, 3]
print("Maximum contiguous sum is", kadane(temperature_change))
				
			

Advantages of Kadane's Algorithm

  1. Efficiency:
    • Time Complexity: Kadane’s Algorithm operates in O(n) time, making it very efficient for large datasets.
    • Space Complexity: It uses O(1) extra space, as it only requires a few additional variables.
  2. Simplicity: The algorithm is straightforward and easy to implement, involving simple iteration and comparison.
  3. Optimality: Kadane’s Algorithm guarantees finding the maximum sum of a contiguous subarray, providing an optimal solution for this specific problem.

Disadvantages of Kadane's Algorithm

  1. Limited Scope:
    • It only solves the maximum subarray sum problem. For different types of subarray problems, modifications or entirely different algorithms might be needed.
  2. Handling Special Cases:
    • In arrays where all elements are negative, Kadane’s Algorithm still works, but it might not be as intuitive.
  3. One-dimensional Focus:
    • Kadane’s Algorithm is designed for one-dimensional arrays. For multi-dimensional arrays or other complex data structures, additional techniques or modifications are required.

Applications of Kadane's Algorithm

  • Stock Market Analysis: To find the best time to buy and sell stocks for maximum profit, Kadane’s Algorithm can be applied to the array of daily price changes.
  • Maximum Subarray Sum: Used in financial analysis, signal processing, and time series analysis to find the period with the maximum sum.
  • Computer Vision: Used in algorithms for finding the largest sum rectangle in a matrix, which can be useful in image processing and computer vision tasks.
  • Genomics: In bioinformatics, it can be used to find regions in DNA sequences that have the highest concentration of a certain property.
  • Data Mining: For identifying patterns or trends in large datasets where the goal is to find contiguous segments with maximum sum or value.

Where Kadane's Algorithm Can Be Used

  1. Dynamic Programming Problems:
    • Kadane’s Algorithm is a classic example of dynamic programming and can be used to introduce the concept.
  2. Optimization Problems:
    • When dealing with optimization problems that require finding maximum sums or values in a linear structure, Kadane’s Algorithm is highly applicable.
  3. Real-time Systems:
    • In systems that require real-time analysis of streaming data to identify peaks or maximum values quickly.
  4. Game Development:
    • In game development, for algorithms that need to determine the best contiguous path or segment with the highest value (e.g., scoring maximum points in a segment).

Code Example for Applications

Here is a simple example demonstrating how Kadane’s Algorithm can be applied to the stock market analysis problem:

				
					def max_profit(prices):
    if not prices:
        return 0
    
    max_profit_so_far = 0
    max_ending_here = 0

    for i in range(1, len(prices)):
        change = prices[i] - prices[i - 1]
        max_ending_here = max(0, max_ending_here + change)
        max_profit_so_far = max(max_profit_so_far, max_ending_here)

    return max_profit_so_far

# Example usage
stock_prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
print("Maximum profit is", max_profit(stock_prices))
				
			

In this example, the max_profit function uses a variation of Kadane’s Algorithm to calculate the maximum profit that can be obtained from buying and selling a stock given daily price changes.

Related Articles

3 thoughts on “Kadane’s Algorithm | Maximum Sum of Contiguous Subarray”

Comments are closed.