# 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.

`dp[i + 1] = max(dp[i], dp[i] + a[i + 1])`

```c++
class Solution {
public:
int maxSubArray(int A[], int n) {
int sum = 0;
int m = INT_MIN;

for(int i = 0; i < n; i++) {
sum += A[i];
m = max(m, sum);
//如果sum小于0了，将sum重置为0，从i + 1再次开始计算
if(sum < 0) {
sum = 0;
}
}

return m;
}
};
```

1. 最大值在A[left, mid - 1]里面
2. 最大值在A[mid + 1, right]里面
3. 最大值跨过了mid，也就是我们需要计算[left, mid - 1]区间的最大值，以及[mid + 1, right]的最大值，然后加上mid，三者之和就是总的最大值

```c++
class Solution {
public:
int maxSubArray(int A[], int n) {
return divide(A, 0, n - 1, INT_MIN);
}

int divide(int A[], int left, int right, int tmax) {
if(left > right) {
return INT_MIN;
}

int mid = left + (right - left) / 2;
//得到子区间[left, mid - 1]最大值
int lmax = divide(A, left, mid - 1, tmax);
//得到子区间[mid + 1, right]最大值
int rmax = divide(A, mid + 1, right, tmax);

tmax = max(tmax, lmax);
tmax = max(tmax, rmax);

int sum = 0;
int mlmax = 0;
//得到[left, mid - 1]最大值
for(int i = mid - 1; i >= left; i--) {
sum += A[i];
mlmax = max(mlmax, sum);
}

sum = 0;
int mrmax = 0;
//得到[mid + 1, right]最大值
for(int i = mid + 1; i <= right; i++) {
sum += A[i];
mrmax = max(mrmax, sum);
}

tmax = max(tmax, A[mid] + mlmax + mrmax);
return tmax;
}
};
```

# Maxmimum Product Subarray

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

> For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

```
maxDP[i + 1] = max(maxDP[i] * A[i + 1], A[i + 1], minDP[i] * A[i + 1])
minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1], maxDP[i] * A[i + 1]
dp[i + 1] = max(dp[i], maxDP[i + 1])
```

```c++
class Solution {
public:
int maxProduct(int A[], int n) {
if(n == 0){
return 0;
} else if(n == 1) {
return A[0];
}

int p = A[0];
int maxP = A[0];
int minP = A[0];
for(int i = 1; i < n; i++) {
int t = maxP;
maxP = max(max(maxP * A[i], A[i]), minP * A[i]);
minP = min(min(t * A[i], A[i]), minP * A[i]);
p = max(maxP, p);
}

return p;
}
};
```