Kadane’s Algorithm in Java

The Kadane algorithm is a dynamic programming algorithm used for finding the maximum subarray sum in a given array of integers. It was proposed by Jay Kadane in 1984 and has a time complexity of O(n), where n is the size of the array.

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, the Kadane algorithm is a simple and efficient algorithm used to solve the maximum subarray problem in a given array of integers. The algorithm has a time complexity of O(n) and requires only a constant amount of additional memory, making it highly efficient in terms of time and space complexity. It is widely used in computer science applications, including image processing, data compression, and bioinformatics. Overall, the Kadane algorithm is a powerful tool for solving the maximum subarray problem and has significant practical applications in various fields.

Frequently Asked Questions

Q1. What is the maximum subarray problem?
Ans. The maximum subarray problem is a well-known problem in computer science that involves finding the subarray of a given array of integers that has the largest sum.

Q2. What is the time complexity of the Kadane algorithm?
Ans. The time complexity of the Kadane algorithm is O(n), where n is the size of the input array.

Q3. Can the Kadane algorithm handle arrays with negative numbers?
Ans. Yes, the Kadane algorithm can handle arrays with negative numbers.

Q4. What are some applications of the Kadane algorithm?
Ans. The Kadane algorithm has various applications in computer science, including image processing, data compression, and bioinformatics. It is also used in financial analysis for portfolio optimization and in machine learning for feature selection.