Kadane's Algorithm (Maximum sum of a subarray)

Given an array of integers, find the maximum sum of a contiguous subarray (at least one element) using Kadane's Algorithm.

Input/Output Examples

Example 1:

  • Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  • Output: 6
    • Explanation: The subarray [4, -1, 2, 1] has the maximum sum of 6.

Example 2:

  • Input: arr = [5, 4, -1, 7, 8]
  • Output: 23
    • Explanation: The entire array forms the subarray with the maximum sum of 23.

Approach for Kadane's Algorithm (Maximum sum of a subarray)

Kadane’s Algorithm is a dynamic programming-based algorithm that solves the maximum subarray sum problem in linear time.

  1. Initialize two variables:
    • max_current: Tracks the current subarray sum (may include negative elements).
    • max_global: Tracks the maximum sum found so far.
  2. Iterate through the array:
    • For each element, either:
      • Start a new subarray with the current element, or
      • Add the current element to the existing subarray (whichever gives a higher sum).
    • Update the global maximum if the current sum exceeds it.
  3. Return the global maximum, which contains the sum of the largest subarray.

C++ Program to implement Kadane's Algorithm

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the maximum subarray sum using Kadane's Algorithm
int kadaneAlgorithm(vector<int> arr) {
    int max_current = arr[0];  // Initialize current subarray sum
    int max_global = arr[0];   // Initialize global maximum sum
    
    for (int i = 1; i < arr.size(); i++) {
        max_current = max(arr[i], max_current + arr[i]); // Update current subarray sum
        if (max_current > max_global) {
            max_global = max_current; // Update global maximum sum
        }
    }
    
    return max_global;
}

int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "The maximum sum of a contiguous subarray is: " << kadaneAlgorithm(arr) << endl;
    return 0;
}

Java Program to implement Kadane's Algorithm

java
public class KadaneAlgorithm {
    // Function to find the maximum subarray sum using Kadane's Algorithm
    public static int kadaneAlgorithm(int[] arr) {
        int maxCurrent = arr[0];  // Initialize current subarray sum
        int maxGlobal = arr[0];   // Initialize global maximum sum
        
        for (int i = 1; i < arr.length; i++) {
            maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);  // Update current subarray sum
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;  // Update global maximum sum
            }
        }
        
        return maxGlobal;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("The maximum sum of a contiguous subarray is: " + kadaneAlgorithm(arr));
    }
}

Python Program to implement Kadane's Algorithm

python
# Function to find the maximum subarray sum using Kadane's Algorithm
def kadane_algorithm(arr):
    max_current = arr[0]  # Initialize current subarray sum
    max_global = arr[0]   # Initialize global maximum sum
    
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])  # Update current subarray sum
        if max_current > max_global:
            max_global = max_current  # Update global maximum sum
    
    return max_global

# Example usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("The maximum sum of a contiguous subarray is:", kadane_algorithm(arr))

Explanation of Code:

  1. Initialization:
    • max_current is initialized to the first element, and max_global also starts with the first element, assuming the array has at least one element.
  2. Iterating through the array:
    • For each element in the array, either:
      • Start a new subarray with the current element (if it's larger than adding it to the previous subarray).
      • Or continue adding it to the existing subarray.
    • If the current subarray sum is greater than the global maximum, update the global maximum.
  3. Return the result: After iterating through the array, max_global will hold the maximum sum of the contiguous subarray.

Time Complexity:

  • O(n): Kadane’s algorithm only requires a single traversal of the array, making it highly efficient.

DSA

2607

402

Related Articles