求最大连续子序列和的四种方法（C语言实现）

这篇博客将介绍四种算法来求解最大连续子序列和，并用C语言实现这四种算法。

---

问题描述

已知n个数A0、A1、A2……An-1。求i、j，使得Ai+Ai+1+……+Aj最大。
举例说明：有8个数4、-3、5、-2、-1、2、6、-2，则这个序列的最大连续子序列的和是4+(-3)+5+(-2)+(-1)+2+6=11。

---

题解

解法一

不难想到，可以通过枚举所有的i和j，求出Ai到Aj的和thisSum，然后与maxSum比较，如果maxSum < thisSum，则将thisSum赋值给maxSum。最后即得到最大连续子序列和。

代码实现如下：

int MaxSubsequenceSum(const int array[], int arraySize)
{
   
    int maxSum = 0;
    int thisSum;

    for (int i = 0; i < arraySize; i++)
    {
   
        for (int j = i; j < arraySize; j++)
        {
   
            thisSum = 0;

            for (int k = i; k <= j; k++)
            {
   
                thisSum += array[k];
            }

            if (maxSum < thisSum)
            {
   
                maxSum = thisSum;
            }
        }
    }

    return maxSum;
}

由于代码中使用了三个for循环，所以不难得出该算法的时间复杂度是O(n^3)。显然这个算法的效率是非常低的，我们需要优化一下。

---

解法二

在上个解法中，我们注意到当i确定时，随着j的递增，需要重复计算从Ai到Aj的和，产生了不必要的计算。所以我们可以把最内层的循环去掉。

代码实现如下：

int MaxSubsequenceSum(const int array[], int arraySize)
{
   
    int maxSum = 0;
    int thisSum;

    for (int i = 0; i < arraySize; i++)
    {
   
        thisSum = 0;

        for (int j = i; j < arraySize; j++)
        {
   
            thisSum += array[j];

            if (maxSum < thisSum)
            {
   
                maxSum = thisSum;
            }
        }
    }

    return maxSum;
}

显然这个算法的时间复杂度是O(n^2)。

---

解法三

对于这个问题，我们还可以使用分治算法来求解。
我们把题目给出数组从中间分为两个子数组，那么最大连续子序列可能有以下三种情况：

1. 最大连续子序列是左边的子数组的子序列；
2. 最大连续子序列是右边的子数组的子序列；
3. 最大连续子序列“跨过”了数组的中点。
   所以我们可以先求出左边子数组的最大连续子序列和和右边子数组的最大连续子序列和以及跨过中点的最大连续子序列和，整个数组的最大连续子序列和即所求三个和的最大值。而对于两个子数组的最大连续子序列和，我们可以递归地求解。

代码实现如下：

int MaxSubSum(const int array[], int left, int right)
{
   
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum = 0, MaxRightBorderSum = 0;
    int LeftBorderSum = 0, RightBorderSum = 0;
    int Center, max;

    if (left == right)
    {
   
        if (array[left] > 0)
        {
   
            return array[left];
        }
        else
        {
   
            return 0;
        }
    }

    Center = (left + right) / 2;
    MaxLeftSum = MaxSubSum(array, left, Center);
    MaxRightSum = MaxSubSum(array, Center + 1, right);

    for (int i = Center; i >= left; i--)
    {
   
        LeftBorderSum += array[i];

        if (MaxLeftBorderSum < LeftBorderSum)
        {
   
            MaxLeftBorderSum = LeftBorderSum;
        }
    }

    for (int i = Center + 1; i <= right; i++)
    {
   
        RightBorderSum += array[i];

        if (MaxRightBorderSum < RightBorderSum)
        {
   
            MaxRightBorderSum = RightBorderSum;
        }
    }

    max = MaxLeftSum > MaxRightSum ? MaxLeftSum : MaxRightSum;
    max = max > (MaxLeftBorderSum + MaxRightBorderSum) ? max : (MaxLeftBorderSum + MaxRightBorderSum);

    return max;
}

int MaxSubsequenceSum(const int array[], int arraySize)
{
   
    return MaxSubSum(array, 0, arraySize - 1);
}

---

解法四

这道题目还可以用动态规划算法来求解：

int maxSubsequenceSum(const int array[], int arraySize)
{
   
    int thisSum, maxSum, i;

    thisSum = maxSum = 0;
    for (int i = 0; i < arraySize; i++)
    {
   
        thisSum += array[i];
        if (thisSum > maxSum)
        {
   
            maxSum = thisSum;
        }
        else if (thisSum < 0)
        {
   
            thisSum = 0;
        }
    }
    return maxSum;
}