**Explanation**

Although there're some other simplified solutions, but DP solution can make the original thought for this problem clearer. In this solution, dp[i] means the largest sum among the subarrays whose last element is A[i].

**Solution1. DP Solution - O(n) time, O(n) space**

```
public int maxSubArray(int[] A) {
int dp[] = new int[A.length]; int max = A[0]; dp[0] = A[0];
for (int i = 1; i < A.length; i++) {
dp[i] = Math.max(dp[i-1] + A[i] ,A[i]);
max = Math.max(max, dp[i]);
}
return max;
}
```

**Solution2. Simplified DP Solution - O(n) time, O(1) space** *- Special thanks for TWiStErRob's smart comment*

The basic idea is to check previous sum, reset it to 0 if it's less than 0.

```
public int maxSubArray(int[] A) {
int res = Integer.MIN_VALUE, sum = 0;
for (int i = 0; i < A.length; i++) {
sum = Math.max(sum, 0) + A[i];
res = Math.max(res, sum);
}
return res;
}
```

**Solution3. Pre-Sum Array Solution - O(n) time, O(n) space**

The basic idea is to use pre-sum array, max = Math.max(max, sum[i] - minSum). (minSum is the minimum sum before A[i])

```
public int maxSubArray(int[] A) {
if (A == null || A.length == 0) return 0;
int max = A[0], minSum = Integer.MAX_VALUE;
int sum[] = new int[A.length];
sum[0] = A[0];
for (int i = 1; i < A.length; i++) {
sum[i] = sum[i-1] + A[i];
minSum = Math.min(0, Math.min(minSum, sum[i-1]));
max = Math.max(max, sum[i] - minSum);
}
return max;
}
```