Kadane's Algorithm

History of Kadane's Algorithm

Kadane's Algorithm was introduced by Joseph Kadane in 1984. It was designed to solve the "Maximum Subarray Problem," a problem in computer science that involves finding the contiguous subarray with the largest sum within a given one-dimensional array of numbers. Kadane's Algorithm is known for its efficiency, reducing the complexity of solving this problem from O(n2) to O(n). The simplicity and effectiveness of the algorithm have made it a fundamental solution for dynamic programming problems and an essential topic in algorithms and coding interviews.

Working of Kadane’s Algorithm

Some of you may think it’ll be a sum of all elements in an array. But what if there will be negative integer elements in the array, which will decrease the array’s total sum.

Thus, we can see that the sum of all elements in an array isn’t always the case.

A simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array and keep track of the maximum sum contiguous subarray among all positive segments. 

• First, we will consider two elements, one which stores the maximum end of the subarray and another which stores the maximum sum so far. 
   
• Let these two variables be temp and final_ans, respectively. 
   
• We will initialise temp to 0 and final_ans to INT_MIN.
   
• Each time we get a positive sum, we compare it with final_ans and update final_ans if it is greater than it.
   

This logic is written in the form of an algorithm as follows:

1. Start
    
2. final_ans = INT_MIN
    
3. temp = 0
    
4. Loop for each element of the array
   
   
   1. if(temp < 0)
      1. temp =  arr[i]
          
   2. else temp = temp + arr[i]
       
   3. if(final_ans < temp)
      1. final_ans = temp
          
5. return final_ans 
    

Let us understand the working better with the same array we considered before:

Initially, max_so_far = max_ending_here = 0. i is the counter for the loop and it is also initialised with 0. 

At the end of all the iterations, the value of final_ans = 11.

Therefore, the maximum contiguous subarray sum is 11.

Brute Force Approach

The brute force solution calculates the sum of each subarray and then compares the results to determine the maximum sum of all subarray sums.

The code for the brute force method would be as follows:

• C++

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {-1,2,-3,4,7,-5};

int n = sizeof(arr)/sizeof(arr[0]);
vector<int>v1;
// To choose the starting point of subarray
for(int i=0;i<n;i++)
{
        // To choose the end point of subarray
        for(int j=i;j<n;j++)
        {
            int temp_sum= 0;
            // Finding the sum of the subarray
            for(int k=i;k<=j;k++)
            {
                temp_sum = temp_sum + arr[k];
            }
            // storing sum in a vector
            v1.push_back(temp_sum);
        }
}

// To print the individual subarray sum..
cout << "Sum of individual Subarray: ";
for (int i = 0; i < v1.size(); i++){
    cout << v1[i] << " ";     
}
cout << endl;

// To print the maximum sum contiguous subarray
cout << "Maximum Sum Contiguous Subarray = "<< *max_element(v1.begin(), v1.end());
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Sum of individual Subarray: -1 1 -2 2 9 4 2 -1 3 10 5 -3 1 8 3 4 11 6 7 2 -5
Maximum Sum Contiguous Subarray = 11

This method is straightforward, but we do not use it commonly. Wondering why?

That is because it has a time complexity of O(N³) and O(N) space complexity.

As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. 

Therefore, we use Kadane’s algorithm because of its advantage considering time and space complexity.

Implementation of Kadane's Algorithm

Next let us look at the implementation of Kadane's algorithm in C, C++, and Java programs. This will help you understand the algorithm better.

C Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in C language.

• C

C

#include <stdio.h>

// Function to find maximum sum contiguous subarray in a given set of integers
int kadane(int arr[], int n) {
   // Stores maximum sum subarray found so far
   int final_ans = INT_MIN;
   // Stores the maximum sum of subarray ending at the current position
   int curr = 0;
   
   // Traverse the given array
   for (int i = 0; i < n; i++) {
   // if maximum sum is negative, set it to current element's value
       if(curr < 0)
     	{
         	curr = arr[i];
     	}
     	// else add it with the current element's value
     	else curr = curr + arr[i];
     	
     	// update result if current subarray sum is found to be greater
     	if(final_ans < curr)
     	{
         final_ans = curr;    
     	}
   }
   return final_ans;
}

int main() {
   int arr[] = {-1,2,-3,4,7,-5};
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("The maximum sum of a contiguous subarray is %d\n", kadane(arr, n));
   return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

The maximum sum of a contiguous subarray is 11

Here, we can see that we iterate the elements linearly. We check if the current sum is negative. If it is found negative we initialize it to be the current element's value, else we add the current element to the current sum. We update the final sum if it is greater than the previous one. Finally, we return the maximum sum of a contiguous subarray found.

Java Implementation of Kadane's Algorithm

The code given below uses Kadane's Algorithm for finding the maximum subarray sum for the array shown above in Java language.

• Java

Java

public class KadaneAlgorithm {
    // Function to find maximum sum contiguous subarray in a given set of integers
    public static int kadane(int[] arr, int n) {
        // Stores maximum sum subarray found so far
        int final_ans = Integer.MIN_VALUE;
        // Stores the maximum sum of subarray ending at the current position
        int curr = 0;

        // Traverse the given array
        for (int i = 0; i < n; i++) {
            // if maximum sum is negative, set it to current element's value
            if (curr < 0) {
                curr = arr[i];
            }
            // else add it with the current element's value
            else {
                curr = curr + arr[i];
            }

            // update result if current subarray sum is found to be greater
            if (final_ans < curr) {
                final_ans = curr;
            }
        }
        return final_ans;
    }

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

You can also try this code with Online Java Compiler

Run Code

Output

The maximum sum of a contiguous subarray is 11

Here also the same approach is followed. Because we are programming it in Java language, we make a class named KadaneAlgorithm. Inside that class, we have the Kadane method to compute the final result.

C++ Implementation of Kadane's Algorithm

The code given below uses Kadane’s Algorithm to find the maximum subarray sum for the array shown above.

• C++

C++

#include<iostream>
#include<climits>
using namespace std;

// Function to find maximum sum contiguous subarray in a given set of integers
int kadane(int arr[], int n){
   // Stores maximum sum subarray found so far
   int final_ans = INT_MIN;
   
   // Stores the maximum sum of subarray ending at the current position
   int curr = 0;
   
   // Traverse the given array
   for (int i = 0; i < n; i++) {
   // if maximum sum is negative, set it to current element's value
       if(curr < 0)
     	{
         	curr = arr[i];
     	}
     	// else add it with the current element's value
     	else curr = curr + arr[i];
     	
     	// update result if current subarray sum is found to be greater
     	if(final_ans < curr)
     	{
         final_ans = curr;    
     	}
   }
   return final_ans;
}

int main()
{
  int arr[] = {-1, 2, -3, 4, 7, -5};
  int n = sizeof(arr)/sizeof(arr[0]);
  cout << "Maximum sum contiguous subarray is "<<kadane(arr, n);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Maximum sum contiguous subarray is 11

Time Complexity: O(N)

Space Complexity: O(1)

We saw that the time complexity of Kadane’s algorithm is less than that of the brute force method when solving the same problem. 

Hence, Kadane’s algorithm is our preferred method when it comes to finding the maximum contiguous subarray sum.

Also Read - Time Complexity of Sorting Algorithms

Applications of Kadane's Algorithm

• Maximum Subarray Problem: Kadane's algorithm is primarily used to find the maximum sum of a contiguous subarray in a given array of integers.
   
• Stock Price Analysis: It can be applied to determine the maximum profit that can be made by buying and selling stocks on specific days.
   
• Dynamic Programming Problems: Kadane’s algorithm serves as an optimization technique in dynamic programming for problems requiring maximum sum calculations.
   
• Image Processing: It is used in image recognition and processing to detect the region with the highest intensity or color variations.
   
• Game Development: Kadane’s algorithm can help identify the most advantageous sequence of moves or actions in games involving score maximization.
   
• Financial Analytics: Helps in analyzing sequences of financial data to identify periods of maximum profit or loss over time.

Advantages of Kadane's Algorithm

Some of the advantages of Kadane's Algorithm are as follows:

• Simplicity: Kadane's Algorithm is comparatively easy to implement and understand from other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm
   
• Space Complexity: This Algorithm has O(1) of space complexity, which means it uses a constant amount of memory despite the size of the input array
   
• Efficiency: Kadane's Algorithm has an O(n) complexity, which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for big datasets
   
• Dynamic Programming: This Algorithm is a great example of dynamic programming. Dynamic programming is a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation

Disadvantages of Kadane's Algorithm

Some of the disadvantages of kadane's Algorithm are as follows:

• Only finds the sum and not the subarray: This Algorithm only finds the maximum sum of the subarray and not the actual subarray. If we want to find the subarray that has the maximum sum, we are required to modify the algorithm accordingly.
   
• Not suitable for non-contiguous subarrays: This Algorithm is specifically designed for contiguous subarrays and is not suitable for non-contiguous subarrays problems.
   
• Does not handle negative value well: If the input contains only negative value, the algorithm returns the maximum negative number instead of 0. 

Frequently Asked Questions

What is the runtime of Kadane’s algorithm?

Kadane's algorithm has O(n) run time. where n is the length of the input array. It is a linear-time algorithm that processes each array element only once and is efficient for large inputs.

What is Kadane's algorithm for maximum product?

Kadane’s algorithm for maximum product is an iterative dynamic programming algorithm in which we search for a maximum product contiguous subarray within a one-dimensional array. Here also keep the basic understanding of Kadane's algorithm to traverse the elements linearly and keep the maximum of the current product and result product as the result.

What is Kadane's algorithm for negative numbers?

For the implementation of Kadane's algorithm, at least one positive number should be present for the final sum. But in cases where all the numbers are negative, we must output the least negative one.

Conclusion

Kadane’s Algorithm is a powerful and efficient solution for finding the maximum sum subarray in linear time. By mastering this algorithm, developers can solve complex array-based problems with ease. Its simplicity and effectiveness make it a fundamental tool in competitive programming and real-world applications alike.

Related Links -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Design and Analysis of Algorithms