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