分治策略

求解递归式方法

最大子数组问题

分治策略

• 分治法流程
• 伪代码

• C++实现

template<typename T>
T FindMaxCrossingSubarray(T* pArray, const int nLenC, int& nBeginPos,
    int& nEndPos)
{
    if (1 == nLenC)
    {
        nBeginPos = 0;
        nEndPos = 0;
        return pArray[0];
    }

    const int nLeftLenC = nLenC / 2;

    T aSum[2] = {};
    T nTemSum = 0;

    for (int i = nLeftLenC - 1; i >= 0; --i)
    {
        nTemSum += pArray[i];
        if (nLeftLenC - 1 == i || aSum[0] < nTemSum)
        {
            aSum[0] = nTemSum;
            nBeginPos = i;
        }
    }

    nTemSum = 0;
    for (int i = nLeftLenC - 1; i < nLenC; ++i)
    {
        nTemSum += pArray[i];
        if (nLeftLenC - 1 == i || aSum[1] < nTemSum)
        {
            aSum[1] = nTemSum;
            nEndPos = i;
        }
    }

    return aSum[0] + aSum[1] - pArray[nLeftLenC - 1];
}

template<typename T>
T FindMaximumSubarray(T* pArray, const int nLenC, int& nBeginPos, 
    int& nEndPos)
{
    if (1 == nLenC)
    {
        nBeginPos = 0;
        nEndPos = 0;
        return pArray[0];
    }

    T aSum[4] = {};
    int aLeftPos[2] = {};
    int aRigthPos[2] = {};
    int aCenterPos[2] = {};
    const int nHalfC = nLenC / 2;

    if (nHalfC)
    {
        aSum[0] = FindMaximumSubarray(pArray, nHalfC, aLeftPos[0],
            aLeftPos[1]);
    }
    
    if (nLenC - nHalfC)
    {
        aSum[1] = FindMaximumSubarray(pArray + nHalfC, nLenC - nHalfC,
            aRigthPos[0], aRigthPos[1]);

        aRigthPos[0] += nHalfC;
        aRigthPos[1] += nHalfC;
    }

    aSum[2] = FindMaxCrossingSubarray(pArray, nLenC, aCenterPos[0],
        aCenterPos[1]);

    if (aSum[0] >= aSum[1] && aSum[0] >= aSum[2])
    {
        nBeginPos = aLeftPos[0];
        nEndPos = aLeftPos[1];
        aSum[3] = aSum[0];
    }
    else if (aSum[1] >= aSum[0] && aSum[1] >= aSum[2])
    { 
        nBeginPos = aRigthPos[0];
        nEndPos = aRigthPos[1];
        aSum[3] = aSum[1];
    }
    else
    {
        nBeginPos = aCenterPos[0];
        nEndPos = aCenterPos[1];
        aSum[3] = aSum[2];
    }

    return aSum[3];
}

线性解

• 流程

template<typename T>
T Better(T* pArray, const int nLenC, int& nBeginPos, int& nEndPos)
{
    T nMaxSum = pArray[0];
    T nSurplusSum = pArray[0];
    int nTemBeginPos = nBeginPos = nEndPos = 0;

    for (int i = 1; i < nLenC; ++i)
    {
        nSurplusSum += pArray[i];

        if (nSurplusSum > nMaxSum)
        {
            nEndPos = i;
            nBeginPos = nTemBeginPos;
            nMaxSum = nSurplusSum;
        }
        else if (nSurplusSum <= 0)
        {
            nSurplusSum = 0;
            nTemBeginPos = i + 1;
        }
    }

    return nMaxSum;
}

代入法求解递归式

递归树法求解递归式

主方法求递归式

以上来自算法导论第四章