Kadan's Algorithm

[AmriteshRaj123]

Kadan's Algorithm Steps :-

Initialise Variables:
maxSoFar to store the maximum sum of any subarray encountered so far, initialized to the smallest possible integer (or arr[0] if the array has at least one element).
maxEndingHere to store the maximum sum of the current subarray, initialized to zero or arr[0].
Iterate Over the Array:
For each element in the array, add it to maxEndingHere.
Update maxSoFar to the maximum of maxSoFar and maxEndingHere.
If maxEndingHere becomes negative, reset it to zero since a negative sum would reduce the potential maximum sum of any subarray including future elements.
Return maxSoFar:

After iterating through the array, maxSoFar will contain the maximum sum of a contiguous subarray.

public class KadanesAlgorithm {
public static int maxSubArraySum(int[] arr) {

if (arr.length == 0) return 0;

int maxSoFar = arr[0];  // Initialize to the first element of the array
int maxEndingHere = arr[0];  // Start with the first element as the initial subarray sum

for (int i = 1; i < arr.length; i++) {
   
    maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
    

    maxSoFar = Math.max(maxSoFar, maxEndingHere);
}

return maxSoFar;

}

public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum Subarray Sum: " + maxSubArraySum(arr));
}
}

Explanation of Changes

Edge Case: The function handles an empty array by returning 0. This can be adjusted based on the specific requirement.

Initialization: maxSoFar and maxEndingHere are both initialized to arr[0] (the first element), which simplifies handling arrays where all elements are negative.

Loop Logic: Instead of adding every element to maxEndingHere, we use Math.max(arr[i], maxEndingHere + arr[i]) to decide whether to start a new subarray at arr[i] or continue with the current one.

This corrected version ensures an efficient
𝑂(n)