Kadane ‘s Algorithm in java

ghz 10months ago ⋅ 143 views

Certainly! Kadane's algorithm is a dynamic programming algorithm used to find the maximum subarray sum in a given array. Here's how it works:

Maximum Subarray Problem:

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

Kadane’s Algorithm:

  1. Initialize two variables:

    • max_so_far to -∞ (or the smallest possible value for the sum)
    • max_ending_here to 0

  2. Iterate through the array:

    • For each element

      num

      :

      • Update max_ending_here to max(num, max_ending_here + num)
      • Update max_so_far to max(max_so_far, max_ending_here)

  3. Finally, max_so_far holds the maximum sum of the subarray.

Kadane Algorithm in Java:

Here's the implementation of Kadane's Algorithm in Java:

public class KadaneAlgorithm {

    public static int maxSubArray(int[] nums) {
        int max_so_far = Integer.MIN_VALUE;
        int max_ending_here = 0;

        for (int num : nums) {
            max_ending_here = Math.max(num, max_ending_here + num);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }

        return max_so_far;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum sum of contiguous subarray: " + maxSubArray(nums));
    }
}

This code defines a method maxSubArray which implements Kadane's Algorithm. It iterates through the array, updating max_ending_here and max_so_far according to the algorithm's logic. Finally, it returns max_so_far, which contains the maximum sum of the subarray.

#algorithm