Contents

1. 1. 最大连续子数组问题

最大连续子数组问题

• 问题：问题描述:给定一个数组A[0,…,n-1]，求A的最大连续子数组，使得该子数组的和最大。

• 例：1, -2, 3, 10, -4, 7, 2, -5 最大连续子数组:3, 10, -4, 7, 2

• 方法一：暴力求解

  • 直接求解A[i,…j]的值

  • 0≤ i < n

  • i≤ j < n

  • i,i+1…,j-1,j的最大长度为n

  • 因此：时间复杂度$O(n^3)$

  • 代码实现：

    //暴力法求解
    int MaxSubArray1(int *A,int n)
    {
        int maxSum = A[0];//最大和
        int start = 0,end = 0;
        int currSum;//当前和 
        for(int i = 0;i<n;++i)
        {
            for(int j = i;j < n;++j)
            {
                currSum = 0;
                //求出从i到j的每一个子数组的和，然后求出最大的一个
                for(int k = i;k<=j;++k)
                {
                    currSum += A[k];
                }
                if(maxSum < currSum)
                {
                    start = i;
                    end = j;
                    maxSum = currSum;
                }
            }
        }
        PrintSubArray(A,start,end);
        return maxSum;
    }
    // 打印数组
    void PrintSubArray(int*A,int start,int end)
    {
        for(int i = start;i <= end;++i)
        {
            cout << A[i] << '\t';
        }
        cout << endl;
    }

• 方法二：分治法

  • 将数组从中间分开，那么最大子数组要么完全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。

  • 完全在左数组、右数组递归解决。

  • 跨立在分界点上：实际上是左数组的最大后缀和右数组的最大前缀的和。因此，从分界点向前扫，向后扫即可。

  • 代码实现：

    //分而治之，分治法求解
    int MaxSubArray2(int *A,int from,int to)
    {
        if(from == to)
            return A[from];
        int middle = (from + to)/2;
        int m1 = MaxSubArray2(A,from,middle);//左半边
        int m2 = MaxSubArray2(A,middle+1,to);//右半边
        // 左半边的后缀
        int  left = A[middle],now = A[middle];
        for (int i = middle - 1; i >= from; --i)
        {
            now += A[i];
            left = max(now,left);
        }
        //右半边的前缀
        int right = A[middle+1];
        now = A[middle + 1];
        for (int i = middle + 2; i <= to; ++i)
        {
            now += A[i];
            right = max(now,right);
        }
        int m3 = left + right;
        return max(m1,m2,m3);
    }
    //比较找最大值函数
    int max(int num1,int num2)
    {
        return num1 > num2 ? num1 : num2;
    }
    
    int max(int num1, int num2,int num3)
    {
        if(num1 > num2)
            return num1 > num3 ? num1 : num3;
        else
            return num2 > num3 ? num2 : num3;
    }

  • 分治法算法复杂度分析

    • 算法的递推关系：T(n)=2×T(\dfrac{n}{2}) + cn（c为常数）
    • 若$n=2^k$,则有
    \begin{eqnarray}T(n) &=&2(2T(\dfrac{n}{4})+c\dfrac{n}{2})+cn\\ &=&4T(\dfrac{n}{4}) + 2cn \\ &=&4(2T(\dfrac{n}{8}) +c\dfrac{n}{4}) + 2cn\\ &=&...\\ &=&2kT(1)+kcn\\ &=&an+cn\log{n} \\ \because n=2^k &\therefore k=\log_{2}{n}\\ \end{eqnarray}
    • 若2^k
    • 所以得：T(n) = Ο(n\log{n})

• 方法三：动态规划

  • 记S[i]为以A[i]结尾的数组中和最大的子数组
  • 则：S[i+1] = max(S[i]+A[i+1], A[i+1])
  • S[0]=A[0]
  • 遍历i： 0≤i ≤n-1
  • 动态规划：最优子问题
  • 时间复杂度：$O(n)$
  • 代码实现：

    //动态规划
    int MaxSubArray3(int *A, int n)
    {
        int result = A[0];
        int sum = A[0];
        int start = 0,end = 0;
        for (int i = 1; i < n; ++i)
        {
            if(sum > 0)
                sum += A[i];
            else
            {
                start = i;
                sum = A[i];
            }
            if (sum > result)
            {
                end = i;
                result = sum;
            }
        }
        PrintSubArray(A,start,end);
        return result;
    }