算法：最大子数组问题的三个解法
首先补充两个数学公式：
什么是最大子数组问题？
给定一数组A, 寻找A中和最大的非空连续子数组。
例如：
输入: A = [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大为 6。
针对该问题，现给出三种解法。
解法一：暴力求解（最直观的方法）
对于长度为 n 的数组A, 任选两个位置作为区间起始和末尾，计算该区间所代表的的子数组的和，选择最大的一个。
符合条件的位置对数有个，因此时间复杂度为
.
由于计算区间和时需要借助一个辅助数组，因此空间复杂度为
代码：
int find_max_subArray( vector<int>& A){
// 构造辅助数组，用来暂存区间和
vector<int> B = A;
for( int i = 1; i < A.size(); i++)
B[i] += B[i-1];
//暴力求解
int res = INT_MIN;
for( int i = 0; i < A.size(); i++)
for( int j = i + 1; j < A.size(); j++)
res = max( max( res, B[j] - B[i]), A[i]);
return res;
}
测试用例：
解法二：分治算法（不好理解且代码长）
假设将数组A[low, …, high] 以位置mid处划分为两个长度大致相等的子数组，则最大子数组A[i, …, j] 必定为以下三种情况之一：
最大子数组完全位于 A[low, …, mid] 之间，即
.
最大子数组完全位于 A[mid, …, high] 之间，即
.
最大子数组跨越了 mid 位置，即
.
三种情况见下图：
代码：
int find_max_subArray( vector<int>& A, int left, int right){
// 处理基准情况
if( left > right)
return INT_MIN;
if(left == right) // 仅有一个元素
return A[left];
int mid = left + (right - left) / 2; // 这样写防止溢出
int L = find_max_subArray( A, left, mid - 1); // 寻找左侧最大和
int R = find_max_subArray( A, mid + 1, right); // 寻找右侧最大和
// 跨过中间位置时
int sum = A[mid], sum_max = A[mid];
for( int i = mid - 1; i >= left; i--){
sum += A[i];
sum_max = max( sum, sum_max);
}
sum = sum_max; // 向另外一侧移动时需要初始化
for( int i = mid + 1; i <= right; i++){
sum += A[i];
sum_max = max( sum, sum_max);
}
return max( max( L, R), sum_max);
}
// 在主程序中输入的参数应该为 find_max_subArray(A, 0, A.size() - 1)
测试用例：
注：该代码已AC LeetCode 第53题。
时间复杂度为：
解法三：动态规划（不易理解但短小精悍）
初始化变量 sum = 0, 从头遍历数组，对于每一个元素 A[i], 变量 sum += A[i], 一旦 sum < 0, 立即让 sum = 0, 并向后移动一个元素，直到数组尾部。最终选择最大的 sum 值。
为直观起见，以数组 A = [-2, 3, -1, 2, -3] 为例：
代码：
int find_max_subArray( vector<int>& A){
int sum = INT_MIN, max_sum = INT_MIN;
for( int i = 0; i < A.size(); i++){
if( sum < 0)
sum = 0;
sum += A[i];
if( max_sum < sum)
max_sum = sum;
}
return max_sum;
}
测试用例：
注：该代码已AC LeetCode 第53题。
由于只是遍历数组，因此时间复杂度为 .