Kadane’s Algorithm in Java

Kadane’s Algorithm is used to find the subarray with the largest sum in a given array of integers. This algorithm operates in O(n) time complexity, making it very efficient for this problem.

Algorithm Explanation

The idea behind Kadane’s Algorithm is to iterate through the array while keeping track of the maximum sum of the subarray that ends at the current position. This is achieved using two variables:

• currentMax: The maximum sum of the subarray that ends at the current position.
• globalMax: The maximum sum of any subarray found so far.

For each element in the array, we update currentMax as the maximum of the current element and the sum of the current element and the previous currentMax. Then, we update globalMax as the maximum of globalMax and currentMax.

Java Code Implementation

// Importing necessary libraries
public class KadanesAlgorithm {

    // Function to find the subarray with the largest sum
    public static int findMaxSubarraySum(int[] nums) {
        // Initialize currentMax and globalMax with the first element of the array
        int currentMax = nums[0];
        int globalMax = nums[0];

        // Iterate through the array starting from the second element
        for (int i = 1; i < nums.length; i++) { // Update currentMax to the maximum of the current element and the sum of current element and currentMax currentMax = Math.max(nums[i], currentMax + nums[i]); // Update globalMax if currentMax is greater than globalMax if (currentMax > globalMax) {
                globalMax = currentMax;
            }
        }

        // Return the globalMax which is the largest sum of subarray found
        return globalMax;
    }

    // Main function to test the algorithm
    public static void main(String[] args) {
        // Example array
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        // Find and print the maximum subarray sum
        int maxSubarraySum = findMaxSubarraySum(nums);
        System.out.println("The maximum subarray sum is: " + maxSubarraySum);
    }
}

Explanation of the Java Code

In the Java code above:

• The function findMaxSubarraySum takes an array of integers as input and returns the sum of the subarray with the largest sum.
• We initialize currentMax and globalMax with the first element of the array.
• We iterate through the array starting from the second element. For each element, we update currentMax and then globalMax if necessary.
• The main function provides an example array and calls the findMaxSubarraySum function to find and print the maximum subarray sum.

Output

For the example array {-2, 1, -3, 4, -1, 2, 1, -5, 4}, the output will be:

The maximum subarray sum is: 6

The subarray with the largest sum is {4, -1, 2, 1} which sums to 6.