算法导论的C++实现——2.分治策略处理最大子数组

一、一般解法（线性求解法）

有一个非分治策略的处理最大子数组的问题，该解法更优雅简洁，并更高效。之所以专门去写分治法是为了更好地理解树形结构。

该方法的核心思想就是当sum小于零就舍弃当前sum，有个小bug就是全为负数，不过很好解决，一下是源代码：

//线性求最大子区间 #include<iostream> using namespace std; constexpr int maxn = 200; const int INF = 0x3f3f3f3f; int main() { int n, a[maxn]; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } int sum = 0; int maxa = -INF; for (int i = 1; i <= n; i++) { sum += a[i]; if (sum > maxa) { maxa = sum; } if (sum < 0) { sum = 0; } } cout << maxa << endl; return 0; }

二、分治策略求解（树形求解法）

A[low…high]的任何连续子数组a[i…j]所处的位置必然是一下三种情况之一：

完全位于子数组A[low…mid]中，因此low<=i<=j<=mid 完全位于子数组A[mid+1…high]中，因此mid<i<=j<=high 跨越了中点，因此low<=i<=mid<=j<=high

过程FindMaxCrossingSubarray接受两个参数l和r，返回一个结构体划定跨越中点的最大子数组的边界，并返回最大子数组中值的和。

Node FindMaxCrossingSubarray(int l, int r) { int leftsum = -inf; int sum = 0; int mid = (l + r) >> 1; int maxleft = mid; int maxright = mid + 1; for (int i = mid; i >= l; i--) { sum = sum + a[i]; if (sum > leftsum) { leftsum = sum; maxleft = i; } } int rightsum = -inf; sum = 0; for (int i = mid + 1; i <= r; i++) { sum = sum + a[i]; if (sum > rightsum) { rightsum = sum; maxright = i; } } Node rten; rten.left = maxleft; rten.right = maxright; rten.sum = leftsum + rightsum; return rten; }

其中Node的定义为边界与和

struct Node { int left = 0; int right = 0; int sum = 0; };

FindMaximumSubarray()则为分解与合并的部分

Node FindMaximumSubarray(int l, int r) { Node rten; Node leftnum, rightnum, crossnum; if (l == r) { rten.left = l; rten.right = r; rten.sum = a[l]; return rten; } int mid = (l + r) >> 1; leftnum = FindMaximumSubarray(l, mid); rightnum = FindMaximumSubarray(mid + 1, r); crossnum = FindMaxCrossingSubarray(l, r); if (leftnum.sum >= rightnum.sum && leftnum.sum >= crossnum.sum) return leftnum; else if (rightnum.sum >= leftnum.sum && rightnum.sum >= crossnum.sum) return rightnum; else return crossnum; }

初始调用函数FindMaximumSubarray()会求出A[1…n]的最大子数组

三、源代码

#include<iostream> #include<vector> using namespace std; constexpr int maxn = 200; constexpr int inf = 0x3f3f3f3f; int a[maxn]; struct Node { int left = 0; int right = 0; int sum = 0; }; Node FindMaxCrossingSubarray(int left, int right); Node FindMaximumSubarray(int left, int right); int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } Node ans; ans = FindMaximumSubarray(1, n); cout << "max left = " << ans.left << "max right = " << ans.right << "sum = " << ans.sum << endl; return 0; } Node FindMaxCrossingSubarray(int l, int r) { int leftsum = -inf; int sum = 0; int mid = (l + r) >> 1; int maxleft = mid; int maxright = mid + 1; for (int i = mid; i >= l; i--) { sum = sum + a[i]; if (sum > leftsum) { leftsum = sum; maxleft = i; } } int rightsum = -inf; sum = 0; for (int i = mid + 1; i <= r; i++) { sum = sum + a[i]; if (sum > rightsum) { rightsum = sum; maxright = i; } } Node rten; rten.left = maxleft; rten.right = maxright; rten.sum = leftsum + rightsum; return rten; } Node FindMaximumSubarray(int l, int r) { Node rten; Node leftnum, rightnum, crossnum; if (l == r) { rten.left = l; rten.right = r; rten.sum = a[l]; return rten; } int mid = (l + r) >> 1; leftnum = FindMaximumSubarray(l, mid); rightnum = FindMaximumSubarray(mid + 1, r); crossnum = FindMaxCrossingSubarray(l, r); if (leftnum.sum >= rightnum.sum && leftnum.sum >= crossnum.sum) return leftnum; else if (rightnum.sum >= leftnum.sum && rightnum.sum >= crossnum.sum) return rightnum; else return crossnum; }

输入：

16 13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7

输出：

max left = 8max right = 11sum = 43