Largest Sum Contiguous Subarray (Kadane’s Algorithm) in Java

When it comes to finding the maximum sum of a contiguous subarray in an array of integers, Kadane’s Algorithm stands out as a highly efficient solution. This algorithm runs in linear time, making it a powerful tool for solving this problem. In this blog post, we’ll dive into the details of Kadane’s Algorithm, understand how it works, and implement it in Java.

Understanding the Problem

Given an array of integers, the task is to find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

For example:

• Input: [-2,1,-3,4,-1,2,1,-5,4]
• Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Kadane’s Algorithm Explained

Kadane’s Algorithm uses a dynamic programming approach to solve the problem. The key idea is to maintain a running sum of the subarray and reset it to zero if it becomes negative. This way, we ensure that the subarray contributes positively to the maximum sum.

Here’s the step-by-step process:

1. Initialize two variables: max_so_far to hold the maximum sum found so far and max_ending_here to store the sum of the current subarray.
2. Iterate through the array.
3. For each element, add it to max_ending_here.
4. If max_ending_here exceeds max_so_far, update max_so_far.
5. If max_ending_here becomes negative, reset it to zero.

Java Implementation

public class KadanesAlgorithm {

    // Method to find the maximum sum of a contiguous subarray
    public static int maxSubArraySum(int[] nums) {
        // Initialize max_so_far to the smallest possible integer value
        // Initialize max_ending_here to 0
        int max_so_far = Integer.MIN_VALUE;
        int max_ending_here = 0;

        // Loop through each element in the array
        for (int num : nums) {
            // Add the current element to the current subarray sum
            max_ending_here += num;

            // Update max_so_far if the current subarray sum is greater
            if (max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }

            // If the current subarray sum becomes negative, reset it to 0
            if (max_ending_here < 0) {
                max_ending_here = 0;
            }
        }

        // Return the maximum sum found
        return max_so_far;
    }

    // Main method to test the algorithm
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = maxSubArraySum(nums);
        System.out.println("Maximum Sum of Contiguous Subarray: " + maxSum);
    }
}

Explanation of the Code

• Initialization: max_so_far is initialized to Integer.MIN_VALUE to ensure it can be updated with the first element. max_ending_here starts at 0 to accumulate the subarray sums.
• Iteration: We loop through each element in the array, adding it to max_ending_here.
• Updating Maximum: If max_ending_here exceeds max_so_far, we update max_so_far.
• Resetting: If max_ending_here drops below 0, it is reset to 0 to discard the negative subarray sum and start fresh.

Conclusion

Kadane’s Algorithm provides an elegant and efficient solution to finding the maximum sum of a contiguous subarray. With a time complexity of O(n), it outperforms other naive methods significantly. The Java implementation provided above showcases how to translate the algorithm into code effectively. Try running the code with different inputs to see the power of Kadane’s Algorithm in action!

Read More …

Solving the Square of a Rotated Array Problem – https://kamleshsingad.com/solving-the-square-of-a-rotated-array-problem/

Differences Between Arrays and Strings in Java – https://kamleshsingad.com/differences-between-arrays-and-strings-in-java/

Mastering Bit Manipulation: Squaring a Number Using Bitwise Operations in Java – https://kamleshsingad.com/mastering-bit-manipulation-squaring-a-number-using-bitwise-operations-in-java/