> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/max-sum-contiguous-subarray.md).

# Max Sum Contiguous Subarray

Find the **contiguous** subarray within an array, **A** of length **N** which has the **largest sum**.

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

**Constraints:**

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

**For example:**

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

Output 1:
    10

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

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

Output 2:
    6

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

```java
public class Solution {
    public int maxSubArray(List<Integer> A) {
        int best = Integer.MIN_VALUE;
        int current = 0;
        for (int i = 0; i < A.size(); i++) {
            current += A.get(i);
            best = Math.max(best, current);
            if (current < 0)
                current = 0;
        }
        return best;
    }
}
```