分治算法

分治策略

• 分解:将问题划分为一些子问题，子问题的形式与原问题一致，只是规模更小
• 解决:递归求解子问题，如果子问题规模足够小，则直接求解
• 合并:将子问题的解组合成原问题的解

最大子数组问题

采用分治法的求解策略:

• 分解:将数组均分为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;
}