### Question

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.

### Stats

Frequency | 3 |

Difficulty | 3 |

Adjusted Difficulty | 4 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This problem can be solved using DP or Divide and Conquer**.

DP solution is very easy. I will only post the code.

**Divide and Conquer approach is difficult**. Not only the idea of solution is hard to come up with, the coding part is even more challenging, **especially when the input array contains all negative numbers**!

### Solution

First 2 code posted below are DP solutions.

**2nd code is from this article (Algorithm 3)**. The idea is to divide the list by half, and find the max of this 3 values:

- max subarray to the left of mid-point (exclusive)
- max subarray to the right of mid-point (exclusive)
- max subarray from left of mid-point to the right of mid-point (inclusive)

For 1 and 2 are easy, for 3 is not. It needs to read left until the end, and right until the end (which means basically read n times). **The total time complexity is O(nlgn)**.

**3rd code is from this blog**. It’s exactly same method, just coding a bit different.

Note there can be negative number! We can not initiate sum to 0. Instead I should do Integer.MIN_VALUE. Meanwhile, the sum should be initiated to 0, and cannot be Integer.MIN_VALUE.

### My code

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

**2nd code**

```
public int maxSubArray(int[] A) {
return recmax(A, 0, A.length - 1);
}
private int recmax(int[] A, int l, int u) {
if (l > u) /* zero elements */
return 0;
if (l == u) /* one element */
return Math.max(Integer.MIN_VALUE, A[l]);
int m = (l + u) / 2;
/* find max crossing to left */
int lmax = Integer.MIN_VALUE;
int sum = 0;
for (int i = m; i >= l; i--) {
sum += A[i];
lmax = Math.max(lmax, sum);
}
int rmax = Integer.MIN_VALUE;
sum = 0;
/* find max crossing to right */
for (int i = m + 1; i <= u; i++) {
sum += A[i];
rmax = Math.max(rmax, sum);
}
return Math.max(Math.max(recmax(A, l, m), recmax(A, m + 1, u)), lmax
+ rmax);
}
```

**3rd code**

```
public int maxSubArray(int[] A) {
return maxArray(A, 0, A.length - 1, Integer.MIN_VALUE);
}
private int maxArray(int A[], int left, int right, int maxV) {
if (left > right) return Integer.MIN_VALUE;
int mid = (left + right) / 2;
int lmax = maxArray(A, left, mid - 1, maxV);
int rmax = maxArray(A, mid + 1, right, maxV);
maxV = Math.max(Math.max(maxV, lmax), rmax);
int sum = 0, mlmax = 0;
for (int i = mid - 1; i >= left; i--) {
sum += A[i];
if (sum > mlmax) mlmax = sum;
}
sum = 0;
int mrmax = 0;
for (int i = mid + 1; i <= right; i++) {
sum += A[i];
if (sum > mrmax) mrmax = sum;
}
maxV = Math.max(maxV, mlmax + mrmax + A[mid]);
return maxV;
}
```