7、給定n個序列，求相鄰的k個數之和為最大

1、問題描述：給定n個數，求相鄰的k個數之和為最大。要求給出複雜度較小的一種算法

再解決這個問題前，先了解一下類似的常見問題。

2、給定一串數字（可正可負的int，放在數組Num裡），要求找到起始位置start和終止位置end，使得從start位置到end位置的所有數字之和最大，傳回這個最大值max。

算法思想：用動态規劃算法實作。

設 iMaxSum 為以 iNumPar[i] 終止且包含 iNumPar[i] 的最大序列的和，有：

   iMaxSum  =  iNumPar[0];

   iMaxSum  =  iMaxSum > 0 ? iMaxSum + iNumPar[i+1] : iNumPar[i+1];

   其中,i = 0,1,...

那麼和iMaxSum 就是 iNumPar[0] ... iNumPar[n] 中最大的一個序列。

算法的時間複雜度為O(n)。

示例代碼

#include <iostream>

using namespace std;

void FindTheMaxSum(int iNumPar[], const int iSize, int &ibegin, int &iend, int &iMaxSum)
{
    ibegin = iend = 0;
    int iTemSum = iNumPar[0], iStart = 0;
    iMaxSum = iTemSum;
    for (int i = 1; i < iSize; ++i)
    {
        if (iTemSum > 0)
        {
            iTemSum = iTemSum + iNumPar[i];
        }
        else
        {
            iTemSum = iNumPar[i];
            iStart = i;
        }
        
        if (iTemSum > iMaxSum) //更新結果
        {
            iMaxSum = iTemSum;
            ibegin = iStart;
            iend = i;
        }
    }
}

int main()
{
    int ibegin = 0, iend = 0, iResult = 0, iCount = 0;
    int iNum[] = {-1, -2, -3, -4, 0, 1, 2, 3, 4, 5, -20, 40, -3};
    iCount = sizeof(iNum)/sizeof(iNum[0]);
    FindTheMaxSum(iNum, iCount, ibegin, iend, iResult);
    cout << ibegin <<" "<< iend <<" "<< iResult <<endl;
    return 1;
}
      

3、最容易想到的就是窮舉搜尋。在n個序列中求出每k個連續序列的值，進行比較。

#include <iostream>

using namespace std;

void FindTheMaxKSum(int iNumPar[], const int iSize, int iK, int &ibegin, int &iend, int &iMaxSum)
{
//iK指出求最大各子序列的長度
    int iTemMaxKsum = 0;
    for (int i = 0; i < iK; ++i)
    {
        iTemMaxKsum += iNumPar[i];
    }
    iMaxSum = iTemMaxKsum;
    
    int iStart = ibegin = 0, iOver = iend = iK - 1;
    for (int i = 1; (i < iSize) && ((iSize - i) >= iK); ++i)
    {
        iTemMaxKsum = 0;
        for (int j = i; ((j - i) < iK) && (j < iSize); ++j)
        {
            iTemMaxKsum += iNumPar[j];
        }

        if (iTemMaxKsum > iMaxSum)
        {
            iMaxSum = iTemMaxKsum;
            ibegin = i;
            iend = i + iK - 1;
        }
    }
}

int main()
{
    int ibegin = 0, iend = 0, iResult = 0, iCount = 0;
    int iNum[] = {-1, -2, 4, 5, 6, 1, 2, 3, 4, -4, -20, 40, -3};
    iCount = sizeof(iNum)/sizeof(iNum[0]);
    FindTheMaxKSum(iNum, iCount, 3, ibegin, iend, iResult);
    cout << ibegin <<" "<< iend <<" "<< iResult <<endl;
    return 1;
}
      

由上可見，複雜度為O(iK + n*k)。

那麼有沒有更好的方法呢？優化的方法就是把循環體内的相加循環去掉。

#include <iostream>

using namespace std;

void FindTheMaxKSum(int iNumPar[], const int iSize, int iK, int &ibegin, int &iend, int &iMaxSum)
{
//iK指出求最大各子序列的長度

    int *pTempSum = new int[iSize];
    pTempSum[0] = iNumPar[0];
    for (int i = 1; i < iSize; i++)
    {
        pTempSum[i] = pTempSum[i - 1] + iNumPar[i]; 
    }
    
    int iStart = ibegin = 0;
    ibegin = 0;
    iend = iK - 1;
    iMaxSum = pTempSum[iend];

    for (int i = 1, j = iK; j < iSize; ++i, ++j)
    {
        if ((pTempSum[j] - pTempSum[i - 1]) > iMaxSum)
        {
            iMaxSum = pTempSum[j] - pTempSum[i - 1];
            ibegin = i;
            iend = j;
        }
    }
delete pTempSum[];
}

int main()
{
    int ibegin = 0, iend = 0, iResult = 0, iCount = 0;
    int iNum[] = {-1, -2, 4, 5, 6, 1, 2, 3, 4, -4, -20, 40, -3};
    iCount = sizeof(iNum)/sizeof(iNum[0]);
    FindTheMaxKSum(iNum, iCount, 3, ibegin, iend, iResult);
    cout << ibegin <<" "<< iend <<" "<< iResult <<endl;
    return 1;
}
      

    由上可見，程式複雜度為O(n)，n為問題規模。

參考