GitHub Viewer
public class KadaneAlgorithm {
// Function to find the maximum subarray sum
public static int maxSubArraySum(int[] arr) {
int maxSoFar = arr[0]; // Initialize to first element
int maxEndingHere = arr[0]; // Max sum ending at current position
for (int i = 1; i < arr.length; i++) {
// Either extend current subarray or start new subarray from current element
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
// Update overall maximum
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
// Driver code to test the algorithm
public static void main(String[] args) {
int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Array elements:");
for (int num : arr) System.out.print(num + " ");
System.out.println();
int maxSum = maxSubArraySum(arr);
System.out.println("Maximum subarray sum is: " + maxSum);
}
}