JavaProgramming/Array/KadaneAlgorithm.java at main · KotlinKing/JavaProgramming · GitHub

29 lines (23 loc) · 1007 Bytes

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);

}

Expand file tree