分治策略
- 分解:将问题划分为一些子问题，子问题的形式与原问题一致，只是规模更小
- 解决:递归求解子问题，如果子问题规模足够小，则直接求解
- 合并:将子问题的解组合成原问题的解
最大子数组问题
采用分治法的求解策略:
- 分解:将数组均分为A、B，则数组的最大子数组必定位于A或者位于B或者跨越了数组中点
- 解决:递归求解位于A与位于B情况下的解
- 合并:对于得到的最大子数组，获取其最大值则就是原问题的解
- 递归式:T(n) = 2T(n / 2) + θ(n)
- 复杂度:nlg(n)
拓展:线性解
设数组A[0, i]的最大子数组为A[a, b]，则数组A[0, i + 1]的最大子数组要么是A[a, b]，要么是A[k, i + 1] (k ≥ a)。潜在的新解k在求A[0, i]的最大子数组A[a, b]的时候可以同步求出。
//寻找最大子数组，允许子数组为空，返回的下标置为-1表示当前最大子数组为空
template<typename T> T FindMaxChildArray(T* pArray, const size_t nLenC,
size_t& nBeginPos, size_t& nEndPos)
{
T nSumMax = 0;
T nSumTem = 0;
size_t k = 0; //新的左侧解
nBeginPos = nEndPos = -1;
for (size_t i = 0; i < nLenC; ++i)
{
nSumTem += pArray[i];
if (nSumTem > nSumMax)
{
nSumMax = nSumTem;
nBeginPos = k;
nEndPos = i;
}
else if (nSumTem <= 0)
{
//之前的左侧解已经不可能是潜在的解了，进行重置
k = i + 1;
nSumTem = 0;
}
}
return nSumMax;
}
