最大子数组结构体
typedef struct { int low, high, sum; } SubArray;暴力求解
计算所有的数组区间的和进而得到最大的子数组,算法复杂度为θ(n²)。这种方法在小规模的数据表现很好,d但是在大规模数据中则很糟糕,但可用作分治算法的改进。实现的思路是先计算从以i为起始的最大子数组,然后从[1..n],[2..n] .. [n..n]中找到最大的子数组。
分治算法
从分治算法的时间分析来看,
$$
T(n)=\begin{cases}
\theta(1) & if & n = 1 \
a\theta(n/a) + \theta(n) & if & n > 1
\end{cases}
$$
如果要寻找[low..high]的最大子数组,使用分治的技术意味我们要将数组分为规模尽可能相等的两个子数组(上a为2),寻找出中间的位置mid,再考虑求解子数组[low..mid]和[mid+1..high]。数组[low..high]的最大子数组[i..j]必然是下面三种情况:
完全位于子数组[low..mid]中,因此low <= i <= high <= mid
完全位于子数组[mid+1..high]中,因此mid+1 <= i <= j <= high
跨域了中点mid,因此位于low <= i <= mid <= j <= high
且规定跨越中点的数组 必须包含mid 和 mid + 1
递归的求解子数组[low..mid]和[mid+1..high],减小子问题问题的规模,最后寻找跨越中点的最大子数组,与归并排序的归并过程相似,我们把寻找跨越中点的最大子数组作为子问题的合并过程。简单的逻辑为
寻找子数组[low..mid]的最大子数组
寻找子数组[mid+1..high]的最大子数组
寻找[low..mid mid+1..high]的最大子数组
返回三个最大子数组中的子数组。注:这里的比较必须要用加上等号,这样可以跳过0更精确的求到最大子数组
SubArray MaxCrossSubArray(int low, int mid, int high, int A[]) { int left_sum, right_sum, sum; SubArray S; left_sum = right_sum = INT_MIN; sum = 0; for (int i = mid; i >= low; i--) { sum += A[i]; if (left_sum < sum) { S.low = i; left_sum = sum; } } sum = 0; for (int j = mid + 1; j <= high; j++) { sum += A[j]; if (right_sum < sum) { S.high = j; right_sum = sum; } } S.sum = left_sum + right_sum; return S; } SubArray MaxSubArray_DivideConquer(int low, int high, int A[]) { if (low == high) { SubArray S; S.low = low; S.high = high; S.sum = A[low]; return S; } int mid = (low + high) / 2; SubArray L = MaxSubArray_DivideConquer(low, mid, A); SubArray R = MaxSubArray_DivideConquer(mid + 1, high, A); SubArray M = MaxCrossSubArray(low, mid, high, A); return Max3(L, R, M); }改进后的递归算法
前面提到暴力求解虽然在大规模数据表现非常差,但是在小规模的求解时优势很大。当子问题的规模小于某个值n时,我们用暴力算法求解
线性算法
已知[1..j]的最大子数组,计算[1..j+1]最大子数组的思路:[1..j+1]的最大子数组要么是[1..j]的最大子数组,要么是某个子数组[i..j+1] (1 <= i <= j+1 )。具体实现如注释所述
写代码时碰到的一些问题
刚开始我的递归实现是还有一个SubArray指针的,但是在内存里面真正的SubArray只有一份,每一次计算SubArray变量都在改变。其实我们只需要子数组的下标与和,所以直接在函数内定义等到函数结束栈内存回收也没有关系,因为已经返回。
暴力算法刚开始的i都是从0开始,如果只是单纯的调用不会产生问题,但是当递归算法小规模取调用的情况下就会出现段错误(越界了)