• 最大子段和

    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

    阅读全文>>
  • 快速幂

    04-25-19

    幂运算是非常常见的一种运算,求a^{n}最容易想到的方法便是通过循环逐个累乘,其复杂度为O(n),这在很多时候是不够的,所以我们需要一种算法来优化幂运算的过程

    快速幂这个东西比较好理解,今天把它系统的总结一下防止忘记.

    首先,快速幂的目的就是做到快速求幂,假设我们要求a^{b},按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(b),即是O(n)级别,快速幂能做到O(logn),快了好多好多.

    它的原理如下:

    假设我们要求a^{b},将b写为二进制的形式,该二进制数第i位的权为2^{i-1}.

    e.g. b=11时, a^{11}=a^{2^{0}+2^{1}+2^{3}}

    11的二进制是1011,11 = 2^{3} \times 1 + 2^{2} \times 0 + 2^{1} \times 1 + 2^{0} \times 1,因此,我们将 a^{11}转化为算 a^{2^{0}}*a^{2^{1}}*a^{2^{3}},也就是a^{1}*a^{2}*a^{8} .原来算11次,现在算三次,但是这三项貌似不好求.

    不急,下面会有详细解释.

    由于是二进制,很自然地想到用位运算这个强大的工具:&(按位与)和>>(右移运算符). &运算通常用于二进制取位操作,例如一个数x& 1 的结果就是取二进制的最末位。还可以判断奇偶,e.g.x&1==0为偶,x&1==1为奇。 >>n运算比较单纯,将数字写成二进制形式,右移n位,即将二进制数去掉最后n位.   

    int binaryPow(int a, int b) {
        int ans = 1, base = a;
        while (b != 0) {
            if (b & 1 != 0)
                ans *= base;
            base *= base;
            b >>= 1;
        }
        return ans;
    }

    代码很短,也很好理解,以b=11为例,11_{10}=1011_{2},二进制从右向左算,但乘出来的顺序是 a^{2^{0}}*a^{2^{1}}*a^{2^{3}},是从左向右的.我们不断的让base*=base目的即是累乘,以便随时对ans做出贡献.

    其中要理解base*=base这一步:因为 base*base  \Longleftrightarrow base^{2},下一步再乘,就是base^{2}* base^{2} \Longleftrightarrow base^{4},然后同理  base^{4}* base^{4} \Longleftrightarrow base^{8},由此可以做到base \longrightarrow base^{2} \longrightarrow base^{4} \longrightarrow base^{8} \longrightarrow base^{16} \longrightarrow base^{32} \cdots指数正是2^{i},再看上面的例子,a^{1}*a^{2}*a^{8},这三项就可以完美解决了.

    如果需要取模的话,直接在每一步运算中对base和ans取模即可.

    阅读全文>>