Largest Sum of Contiguous Subarray

public class LargestSumContiguousSubarray {
    // Function to find the maximum sum of a contiguous subarray
    public static int maxSubArraySum(int[] arr) {
        int maxSoFar = arr[0]; // This will store the result (maximum sum)
        int currentMax = arr[0]; // This will store the current subarray sum

        // Traverse the array from the second element
        for (int i = 1; i < arr.length; i++) {
            // Update currentMax to the larger of either the current element alone or adding the current element to currentMax
            currentMax = Math.max(arr[i], currentMax + arr[i]);

            // Update maxSoFar to be the maximum of itself and currentMax
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        return maxSoFar; // Return the final maximum sum
    }

    public static void main(String[] args) {
        // Example test case
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = maxSubArraySum(arr);
        System.out.println("The largest sum of contiguous subarray is: " + maxSum);
    }
}