Max Sum Contiguous Subarray (Kadane’s Algorithm)

1 <= N <= 1e6
-1000 <= A[i] <= 1000

The first and the only argument contains an integer array, A.

Return an integer representing the maximum possible sum of the contiguous subarray.

Input 1:
A = [1, 2, 3, 4, -10] 

Input 2:
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output 1:
10

Output 2:
6

Explanation 1:
The subarray [1, 2, 3, 4] has the maximum possible sum of 10.

Explanation 2:
The subarray [4,-1,2,1] has the maximum possible sum of 6. 

public class MaxSumContiguousSubarray {
    public int maxSubArray(int[] A) {
        int maxSum = A[0];
        int currentSum = A[0];
        
        for (int i = 1; i < A.length; i++) {
            currentSum = Math.max(A[i], currentSum + A[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

def maxSubArray(A):
    max_sum = A[0]
    current_sum = A[0]
 
    for num in A[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
 
    return max_sum

function maxSubArray(A) {
    let maxSum = A[0];
    let currentSum = A[0];
    
    for (let i = 1; i < A.length; i++) {
        currentSum = Math.max(A[i], currentSum + A[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}