算法导论 - 最大子数组

老王

我们思考如何使用分治技术来求解最大子数组问题。假设我们要寻找数组A[low...high]中的最大子数组。使用分治技术意味着我们要将数组划分为两个规模尽量相等的子数组。也就是说，找到数组的中间位置，比如mid，然后求解两个子数组A[low...mid]和A[mid + 1...high]。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。

A[low...high]数组中的一个最大子数组所处的位置必然是这三种情况之一，也就是说A[low...high]中的一个最大子数组必然是完全位于A[low...mid]中、完全位于A[mid + 1...high]中或跨越中点的。我们可以递归地求解A[low...mid]和A[mid + 1...high]中的最大子数组，这两个子问题仍是最大子数组问题，只是规模更小；剩下的工作就是寻找跨越中点的最大子数组，然后在这三种情况中选取和最大的那个。

[C++] 纯文本查看 复制代码

#include <Windows.h>
#include <stdio.h>

typedef struct StructSubArray
{
    size_t nLow;
    size_t nHigh;
    int    nSum;
}StructSubArray, * PStructSubArray;

void FindMaxCrossingSubArray(int arrInt[], size_t nLow, size_t nMiddle, size_t nHigh, PStructSubArray pSubArray)
{
    int    nLeftSum = INT_MIN;
    int    nSum     = 0;
    size_t nMaxLeft = pSubArray->nLow;
    for (size_t i = nMiddle; i >= nLow; i--)
    {
        nSum += arrInt[i];
        if (nSum > nLeftSum)
        {
            nLeftSum = nSum;
            nMaxLeft = i;
        }

        if (i == 0)
            break;
    }

    int    nRightSum = INT_MIN;
    size_t nMaxRight = pSubArray->nHigh;
    nSum = 0;
    for (size_t i = nMiddle + 1; i <= nHigh; i++)
    {
        nSum += arrInt[i];
        if (nSum > nRightSum)
        {
            nRightSum = nSum;
            nMaxRight = i;
        }
    }

    pSubArray->nLow  = nMaxLeft;
    pSubArray->nHigh = nMaxRight;
    pSubArray->nSum  = nLeftSum + nRightSum;
}

void FindMaxSubArray(int arrInt[], size_t nLow, size_t nHigh, PStructSubArray pSubArray)
{
    if (nLow == nHigh)
    {
        pSubArray->nLow  = nLow;
        pSubArray->nHigh = nHigh;
        pSubArray->nSum  = arrInt[nLow];
    }
    else
    {
        size_t nMiddle = (nLow + nHigh) / 2;

        StructSubArray subArrayLeft = { 0 };
        FindMaxSubArray(arrInt, nLow, nMiddle, &subArrayLeft);
        StructSubArray subArrayRight = { 0 };
        FindMaxSubArray(arrInt, nMiddle + 1, nHigh, &subArrayRight);
        StructSubArray subArrayCross = { 0 };
        FindMaxCrossingSubArray(arrInt, nLow, nMiddle, nHigh, &subArrayCross);

        if (subArrayLeft.nSum >= subArrayRight.nSum && subArrayLeft.nSum >= subArrayCross.nSum)
        {
            pSubArray->nLow  = subArrayLeft.nLow;
            pSubArray->nHigh = subArrayLeft.nHigh;
            pSubArray->nSum  = subArrayLeft.nSum;
        }
        else if (subArrayRight.nSum >= subArrayLeft.nSum && subArrayRight.nSum >= subArrayCross.nSum)
        {
            pSubArray->nLow  = subArrayRight.nLow;
            pSubArray->nHigh = subArrayRight.nHigh;
            pSubArray->nSum  = subArrayRight.nSum;
        }
        else
        {
            pSubArray->nLow  = subArrayCross.nLow;
            pSubArray->nHigh = subArrayCross.nHigh;
            pSubArray->nSum  = subArrayCross.nSum;
        }
    }
}

int main()
{
    int arrInt[] = { 88, -100, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, -1, -2, -3, -4, -5 };
    size_t nCount = sizeof(arrInt) / sizeof(arrInt[0]);

    StructSubArray subArray = { 0 };
    FindMaxSubArray(arrInt, 0, nCount - 1, &subArray);

    for (size_t i = subArray.nLow; i <= subArray.nHigh; i++)
        printf("%d\n", arrInt[i]);

    return 0;
}