Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[−2,1,−3,4,−1,2,1,−5,4]`

,

the contiguous subarray `[4,−1,2,1]`

has the largest sum = `6`

.

**More practice:**If you have figured out the O(*n*) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Thinking: Using DP, there is a pattern that for subarray 0-i, the maximum subarray is the maximum in this subarray. Therefore we need to keep one max that keeps track on what is the first maximum subarray so far.

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

Advertisements