# [leetcode] Maximum Subarray

### Maximum Subarray

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.

O(N)算法

```class Solution {
public:
int maxSubArray(int A[], int n) {
int sum = A[0];
int biggest = A[0];
for(int i = 1; i < n; i++){
if(sum < 0){
sum = A[i];
}
else{
sum += A[i];
}
biggest = biggest < sum? sum: biggest;
}
return biggest;
}
};```

O（nlogn）算法

```class Solution {
public:
int maxSubArray(int A[], int n) {
return _maxSubArray(A, 0, n);
}
//[left, right)
int _maxSubArray(int A[], int left, int right){
//base case
if(right - left == 1){
return A[left];
}
int mid = (left + right) / 2;
int a = _maxSubArray(A, left, mid);
int b = _maxSubArray(A, mid, right);
int sum = 0;
for(int i = mid - 1; i >=left; i--){
if(i == mid - 1) maxLeftAdjacent = A[i];
sum += A[i];
}
sum = 0;
for(int i = mid; i < right; i++){
if(i == mid) maxRightAdjacent = A[i];
sum +=A[i];