Data Structure & Algorithms
Arrays One Dimensional
Max Sum Contiguous Subarray

# Max Sum Contiguous Subarray (Kadane’s Algorithm)

## Problem Description

Find the maximum sum of contiguous non-empty subarray within an array A of length N.

### Problem Constraints

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

### Input Format

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

### Output Format

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

### Example Input

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

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

### Example Output

``````Output 1:
10

Output 2:
6``````

### Example Explanation

``````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. ``````

### Output

Java
``````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;
}
}``````
Python
``````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``````
JavaScript
``````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;
}``````