Kadane’s Algorithm in Java

Last Updated on December 28, 2023 by Ankit Kochar

Kadane’s Algorithm is a fundamental algorithm in computer science used for efficiently finding the maximum subarray sum in a given array of numbers. This algorithm was introduced by Ulf Grenander and later independently discovered by Jay Kadane. It has widespread applications in various fields, such as image processing, data analysis, and algorithmic problem-solving. Kadane’s Algorithm is known for its simplicity and effectiveness, providing a linear-time solution to the maximum subarray sum problem.

How does Kadane’s Algorithm Work?

The idea behind the Kadane algorithm is to maintain two variables: maxSoFar and maxEndingHere. The maxSoFar variable keeps track of the maximum subarray sum found so far, while the maxEndingHere variable keeps track of the maximum subarray sum ending at the current position.

The algorithm iterates through the array and updates the maxEndingHere variable at each position. If the maxEndingHere variable becomes negative, it is reset to zero, as a negative subarray sum cannot contribute to the maximum subarray sum. The maxSoFar variable is updated if the maxEndingHere variable is greater than it.

At the end of the iteration, the maxSoFar variable contains the maximum subarray sum.

For example, if we have an array like [-3, -4, 5, -1, 2, -4, 6, -1], then Subarray [5, -1, 2, -4, 6] is the max sum contiguous subarray with sum 8.

Approaches for Kadane’s Algorithm

We have different approaches for Kadane’s Algorithm:

Naive Approach

Running two for loops and checking each subarray’s maximum total for each subarray is the simplest way to handle this problem.

Algorithm

• Step 1: Run a loop for i between 0 and n – 1, where n is the array’s size.
• Step 2: The value of the element at position j will now be added to a variable called currentMax when we execute a nested loop for j from i to n – 1.
• Step 3: Finally, we will determine for each subarray if the currentMax is the greatest total of all adjacent subarrays.

Code Implementation

import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    public static int maximumSubarraySum(int[] arr) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;

        for (int i = 0; i <= n - 1; i++) {
            int currSum = 0;
            for (int j = i; j <= n - 1; j++) {
            currSum += arr[j];
            if (currSum > maxSum) {
                maxSum = currSum;
            }
            }
        }

        return maxSum;
    }
    public static void main(String args[]) {
        
        int a[] = {1, 3, 8, -2, 6, -8, 5};
        System.out.println(maximumSubarraySum(a));
    }
}

Output

16

Efficient Approach

An iterative dynamic programming algorithm is Kadane’s Algorithm. Using the maximum sum subarray ending at the position before determines the maximum sum subarray ending at a certain location.

Algorithm

• Step 1: Define the two variables maxSum, which holds the maximum sum to date, and currSum, which stores the maximum amount up to this point.
• Step 2: Set currSum to 0 and maxSum to INT_MIN upon initialization.
• Step 3: Add the value of the current element to currSum as you cycle through the array now, then verify
  • Update maxSum equal to currSum if currSum exceeds maxSum.
  • Make currSum equal to zero if it is less than zero.
• Step 4: Print maxSum’s value to finish.

Code Implementation

import java.util.*;
import java.io.*;

class Main {
    public static int maximumSubarraySum(int[] arr) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;
        int currSum = 0;

        for (int i = 0; i <= n - 1; i++) {
            currSum += arr[i];

            if (currSum > maxSum) {
            maxSum = currSum;
            }

            if (currSum < 0) {
            currSum = 0;
            }
        }

        return maxSum;
    }


    public static void main(String args[]) {

        int a[] = {1, 3, 8, -2, 6, -8, 5};
        System.out.println(maximumSubarraySum(a));
    }
}

Output

16

Conclusion
In conclusion, Kadane’s Algorithm has proven to be an invaluable tool in solving the maximum subarray sum problem efficiently. Its linear-time complexity makes it well-suited for real-world applications where optimizing the performance of algorithms is crucial. By elegantly traversing the array and maintaining local and global maximum subarray sums, Kadane’s Algorithm provides an elegant solution to a problem that arises in diverse areas of computer science and beyond.
Understanding and implementing Kadane’s Algorithm is not only beneficial for algorithmic problem-solving but also contributes to a deeper appreciation of dynamic programming techniques. As developers encounter scenarios requiring the identification of maximum subarray sums, Kadane’s Algorithm remains a reliable and widely adopted solution.

FAQs related to Kadane’s Algorithm

Here are some frequently asked questions (FAQs) about Kadane’s algorithm:

Q1: What is the maximum subarray sum problem?
A1: The maximum subarray sum problem involves finding the contiguous subarray within a given array of numbers that has the largest sum. Kadane’s Algorithm efficiently solves this problem and is widely used for its simplicity and effectiveness.

Q2: How does Kadane’s Algorithm work?
A2: Kadane’s Algorithm traverses the array of numbers, maintaining the maximum sum of subarrays encountered so far. It uses dynamic programming principles by keeping track of the local maximum sum at each position and updating the global maximum sum accordingly. The final global maximum sum represents the solution to the maximum subarray sum problem.

Q3: What is the time complexity of Kadane’s Algorithm?
A3: Kadane’s Algorithm has a time complexity of O(n), where n is the length of the input array. This linear-time complexity makes it an efficient solution for large datasets.

Q4: Can Kadane’s Algorithm handle arrays with all negative numbers?
A4: Yes, Kadane’s Algorithm can handle arrays with all negative numbers. It returns zero if the array consists entirely of negative numbers, indicating that the maximum subarray sum is an empty subarray. This behavior is consistent with the definition of the problem.

Q5: Are there variations or optimizations of Kadane’s Algorithm?
A5: While Kadane’s Algorithm is highly efficient, there are variations and optimizations that address specific requirements or constraints. One example is the "circular subarray sum" problem, for which modifications to Kadane’s Algorithm can be applied.

Q6: In what scenarios is Kadane’s Algorithm commonly used?
A6: Kadane’s Algorithm is commonly used in scenarios where finding the maximum subarray sum is essential, such as financial data analysis, image processing, and any application involving the efficient analysis of sequential data.