• 最大子段和

    05-19-19

    最大子段和问题

    一、问题描述:

    给定由n个整数组成的序列a_{1},a_{2},\cdots,a_{n},求该序列子段和的最大值。当所有整数均为负值时,定义其最大子段和为0.

    由此定义,可以得出所求的最优值为:

    \max \{0, \max\limits_{1 \leq i \leq j \leq n} \sum\limits_{k=i}^{j} a_{k} \}

    例如,当( a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6})=(-2,11,-4,13,5,-2)时,最大子段和为a_{2}+a_{3}+a_{4}=11-4+13=20

    二、一个简单算法

    int MaxSum(int n, int a[], int& besti, int& bestj)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                int thissum = 0;
                for (int k = i; k <= j; k++)
                    thissum += a[k];
                if (thissum > sum)
                {
                    sum = thissum;
                    besti = i + 1;
                    bestj = j + 1;
                }
            }
        return sum;
    }//时间复杂度O(n3)
    //main函数
    int main()
    {
        int a[] = { -2,11,-4,13,-5,-2 };
        int sum = 0, besti = 0, bestj = 0;
        sum = MaxSum(sizeof(a) / sizeof(int), a, besti, bestj);
        cout << "Sum from " << besti << " to " << bestj << endl;
        cout << "The sum is " << sum << endl;
        return 0;
    }

    运行结果:

    1558232847886814.png




    三、简单算法的改进

    int MaxSum(int n, int a[], int& besti, int& bestj) //简单算法的改进
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            int thissum = 0;
            for (int j = i; j < n; j++)
            {
                thissum += a[j];
                if (thissum > sum)
                {
                    sum = thissum;
                    besti = i + 1;
                    bestj = j + 1;
                }
            }
        }
        return sum;
    }//时间复杂度O(n2)

    运行结果:

    1558232894395881.png




    四、分治算法

    将最大子段和a[1:n]分为a[1:n/2]a[n/2 + 1:n]两段,则可能有以下三种情况:

    1) a[1:n]的最大子段和 = a[1:n/2]的最大子段和

    2) a[1:n]的最大子段和 = a[n/2 + 1:n]的最大子段和

    3) a[1:n]的最大子段和\sum\limits_{k=i}^{j}a_{k},1 \leq i \leq n/2, n/2+1 \leq j \leq n

    此时,可分别计算a[1:n/2]a[n/2 + 1:n]的最大子段和s1=\max\limits_{1 \leq i \leq n/2} \sum\limits_{k=i}^{n/2}a[k]s2=\max\limits_{n/2+1 \leq i \leq n} \sum\limits_{k=n/2+1}^{i}a[k]

    int MaxSubSum(int a[], int left, int right, int &besti, int &bestj)
    {
        int sum = 0;
        if (left == right) sum = a[left] > 0 ? a[left] : a[0]; //递归出口
        else
        {
            int center = (left + right) / 2;
            int leftsum = MaxSubSum(a, left, center,besti,bestj);
            int rightsum = MaxSubSum(a, center + 1, right,besti, bestj);
            int s1 = 0, lefts = 0;
            for (int i = center; i >= left; i--)
            {
                lefts += a[i];
                if (lefts > s1)
                {
                    s1 = lefts;
                    besti = i + 1;
                }
            }
            int s2 = 0, rights = 0;
            for (int i = center + 1; i <= right; i++)
            {
                rights += a[i];
                if (rights > s2)
                {
                    s2 = rights;
                    bestj = i + 1;
                }
            }
            sum = s1 + s2;
            if (sum < lefts) sum = leftsum;
            if (sum < rightsum) sum = rightsum;
        }
        return sum;
    }
    int main()
    {
        int a[] = { -2,11,-4,13,-5,-2 };
        int sum = 0, besti = 0, bestj = 0;
        
        sum = MaxSubSum(a, 0, 5, besti, bestj);
        cout << "Sum from " << besti << " to " << bestj << endl;
        cout << "The sum is " << sum << endl;
        return 0;
    }

    运行结果:

    1558232984320001.png




    复杂性分析:

    T(n)=\begin{cases}O(1), & \text{if} \quad n \leq c;\\2T(n/2)+O(n), & \text{if} \quad n > c\end{cases}

    即每个问题可以分为两个n/2的子问题,其中的O(n)为从center处遍历每个节点,求解最优解的过程。

    由主定理,可得出T(n) = O(nlogn)

    五、动态规划算法

    b_{j}=\max\limits_{1 \leq i \leq j}\sum\limits_{k=i}^{j}a_{k},(1 \leq j \leq n),表示a[1…j]的前j个元素中最大子段和,则b_{j-1}表示a[1…j-1]的前j-1个元素中的最大子段和,如下所示

    \underbrace{\overbrace{a_{1} \quad a_{2} \quad \cdots \quad a_{j-1}}^{b_{j-1}} \quad a_{j}}_{b_{j}} \quad \cdots \quad a_{n}

    显然,当b_{j-1}>0时,b_{j}=b_{j-1}+a_{j};b_{j-1} \leq 0时,放弃前面选取的元素,从a_{j}开始重新选取,b_{j}=a_{j}。用一维动态规划数组dp存放b,对应的状态方程如下

    \begin{cases}dp[0]=0 &\\dp[j]=\max\{dp[j-1]+a_{j},a_{j}\}, & 1 \leq j \leq n\end{cases}

    则序列a的最大子段和等于\max\limits_{1 \leq j \leq n}dp[j]

    从中看到,若序列a的最大子段和等于dp[maxj],在dp中从该位置向前找,找到第一个值小于或等于0的元素dp[k],则a序列中从k+1开始到maxj位置的所有元素恰好构成最大子段和序列。

    例如,若a序列为(-2,11,-4,13,-5,-2)dp[0]=0,求其他元素如下:

    1dp[1]=max{dp[0]+(-2),-2}=max{-2,-2}=-2

    2dp[2]=max{dp[1]+11,11}=max{9,11}=11

    3dp[3]=max{dp[2]+(-4),-4}=max{7,-4}=7

    4dp[4]=max{dp[3]+13,13}=max{20,13}=20

    5dp[5]=max{dp[4]+(-5),-5}=max{15,-5}=15

    6dp[6]=max{dp[5]+(-2),-2}=max{13,-2}=13

    其中,dp[4]=20为最大值,向前找到dp[1]小于等于0,所以由a_{2}~a_{4}的元素即(11,-4,13)构成最大子段和,其和为20

    #include<iostream>
    using namespace std;
    #define max(x,y) ((x)>(y) ? (x):(y))
    #define MAXN 20
    //问题表示
    int n = 6;
    int a[] = { 0,-2,11,-4,13,-5,-2 }; //a[0]不使用
    int dp[MAXN];
    //求dp数组
    void maxSubSum()
    {
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            dp[i] = max(dp[i - 1] + a[i], a[i]);
    }
    //输出结果
    void dispmaxSum()
    {
        int maxj = 1;
        int k = 0; //k用于存放dp中从maxj向前遍历,第一个值小于等于0的下标
        for (int j = 2; j <= n; j++)
            if (dp[j] > dp[maxj])
                maxj = j;
        for (k = maxj; k >= 1; k--)
            if (dp[k] <= 0)  break;
        cout << "最大子段和:" << dp[maxj] << endl;
        cout << "所选子段:";
        for (int i = k + 1; i <= maxj; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    int main()
    {
        maxSubSum();
        cout << "求解结果如下" << endl;
        dispmaxSum();
        return 0;
    }

    运行结果:

    1558233095570238.png

    更多
  1. 小耗子说道:

    沙发沙发
    小黑特腻害
    小黑特棒棒

  2. Hankai说道:

    小小小黑特,加油鸭!踩一踩,以后这里可能是大佬博客。留个爪,嘻嘻嘻。

请写一条留言给我们