2014
11-19

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

click to show more practice.

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.

\begin{eqnarray}
f[j] &=& \max\left\{f[j-1]+S[j],S[j]\right\}, \text{ 其中 }1 \leq j \leq n \nonumber \\
target &=& \max\left\{f[j]\right\}, \text{ 其中 }1 \leq j \leq n \nonumber
\end{eqnarray}

\item 情况一，S[j]不独立，与前面的某些数组成一个连续子序列，则最大连续子序列和为$f[j-1]+S[j]$。
\item 情况二，S[j]独立划分成为一段，即连续子序列仅包含一个数S[j]，则最大连续子序列和为$S[j]$。

\item 思路2：直接在i到j之间暴力枚举，复杂度是$O(n^3)$
\item 思路3：处理后枚举，连续子序列的和等于两个前缀和之差，复杂度$O(n^2)$。
\item 思路4：分治法，把序列分为两段，分别求最大连续子序列和，然后归并，复杂度$O(n\log n)$
\item 思路5：把思路2$O(n^2)$的代码稍作处理，得到$O(n)$的算法
\item 思路6：当成M=1的最大M子段和

// LeetCode, Maximum Subarray
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
int maxSubArray(int A[], int n) {
int result = INT_MIN, f = 0;
for (int i = 0; i < n; ++i) {
f = max(f + A[i], A[i]);
result = max(result, f);
}
return result;
}
};


// LeetCode, Maximum Subarray
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
int maxSubArray(int A[], int n) {
return mcss(A, n);
}
private:
// 思路5，求最大连续子序列和
static int mcss(int A[], int n) {
int i, result, cur_min;
int *sum = new int[n + 1];  // 前n项和

sum[0] = 0;
result = INT_MIN;
cur_min = sum[0];
for (i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + A[i - 1];
}
for (i = 1; i <= n; i++) {
result = max(result, sum[i] - cur_min);
cur_min = min(cur_min, sum[i]);
}
delete[] sum;
return result;
}
};


1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确