对最大子段和算法的实例评述
首页 > 杂记    作者:StanWind   2018年1月30日 8:00 星期二   热度:4859°   百度已收录  
时间:2018-1-30 8:00   热度:4859° 

<p class"1"="" style="text-indent:-18.0pt;">


一.  基本理论、特点

(一)问题描述

      给定n个整数(可能为负数)组成序列a1,a2,a3…,an,求该序列形如1.png

(二)基本理论

      首先想到的解决算法就是穷举,枚举出所有情况然后比较子段和大小得出结果,这其中得出所有情况的和过程中,计算有重复可以稍加分析优化;然后是分治法,把这一串序列不断细化,求解出每一段的子段和进行比较得出结果。

(三)特点

      需要求子段和需要前后两个下标位置,穷举法得出结果复杂度必然很高;分治法求解时会发生结果出现在分开处,需要考虑这一段的最大子段和求解,复杂度将会大于等于O(nlogn)。

 

二.  求解过程

求一下序列的最大字段和:

   【 31 40 -38 41 13 -41 -23 4 45 46 -35 47 45 -2 30 -36 -8 41 29 45 15 -47 34 43 17 25 24-11 15-33 20-47 -23-46-41 32 19-19 45-47 -7-12 26 29-32 -2 -6 14 20 25-23 17 15-34-39 -1 45-16 8- 28 25-25 0 19 39 45 4-37-36-25 34- 25 31-26 42-16-31-25 11 -3 -15 33 8 4 41-22 25 25-12 6-43-45 3 27 43-38 6 -4-49-17

(一)分析问题

      这里给定了100个整数,需要求解出最大子段和。这个问题其实就是从给定的一串序列中求其子连续序列的最大值。那么可以用sum(i,j)来表示a[i]+a[i+1]+…+a[j] (0>=i>=j>=n),那么经过穷举过后就可以比较得出最大子段和。

(二)算法设计与论证

1.穷举法

      如上面求解分析所说,只需要枚举出所有可能的i,j后进行求和就能得出结果。但是枚举出所有可能就有两层循环,之后计算i->j的和又有一层循环,复杂度是O(n3)。

2.分治法

      分治法求解这个问题无非就是将序列不断细分,这题中分解成左右两部分,但是最大子段和可能发生在任何几个连续数之间,即结果也可能发生在分解序列之间。则left_max = max(left,center),right_max=max(center+1,right),center_max=sum(i,j) (i<=center<=j)。

3.动态规划法

      如上穷举法求和方面计算sum(i,j)之后需要继续计算sum(i,j+1),如果更改循环结构,并且存储好上次结果能很好的降低复杂度。这样的话不难得出sum(i,j) = sum(i,j-1)+a[j]。

那么在最大值方面,如果sum(i,j-1)>=0,那么下个值sum(i,j)则可能选为最大值,即max(i,j);如果sum(i,j-1)<0,那么下个推算出的最大值应为max(i,j)=a[j]。那么只需要遍历一遍该序列就可以得出结果,复杂度为O(n)。

(三)伪代码

1.动态规划

 

function <max>(a[N] Integer)

   m[N] Integerß{0}

   maxß0

   for iß1 to N do

if m[i-1]>0 then

   m[i]=m[i-1]+a[i]

else

   m[i]=a[i]

end if

if b[i]>max then

   max=b[i]

end if

   end for

return max

 

 

2.分治法

 

function <max>(left Integer,right Integer)

l_max,r_max,max,l_sum,r_sum,sumß0

if left = right then

    if a[left] > 0 then

        return a[left]

    else

        return 0

    end if

else

    l_max = max(left,center)

    r_max = max(center+1,right)

    for i:=1 to left do

        sum=sum+a[i]

        if sum > l_sum then

             l_sum=sum

        end if

     end for

     sumß0

     for i:=center+1 to right do

         sum=sum+a[i]

        if sum > r_sum then

             r_sum=sum

        end if

     end for

     max = l_sum+r+sum

     if l_max>max then

          max = l_max

     end if

     if r_max>max then

          max = r_max

     end if

 end if

return max

 

(四)问题求解

1.算法实现(C语言)

1动态规划

#include<stdio.h>

#define MAX 100

int maxsub(int left,int right);

int a[MAX];

int main(){

    int i;

    int count;

    scanf("%d",&count);

    for(i=0;i<count;i++)

    {

        scanf("%d",&a[i]);

    }

   

    //DP

    // 创建存储和的数组

    int m[MAX] = {0};

    m[0] = a[0];

    //如果前段和>0 则下一个最大和为前段加下个值 否则为下个值

    int max = 0;

    for(int i=1;i<count;i++){

        if(m[i-1]>0){

            m[i]=b[i-1]+a[i];

        }

        else{

            m[i]=a[i];

        }

        //然后判断这次是不是最大值

        max = m[i]>max?m[i]:max;

    }

    printf("max = %d \n",max);

   

    return 0;

}

 

2分治法

 

int maxsub(int left,int right) {

    int l_max,r_max,max = 0;

    int l_sum=0,r_sum=0,sum = 0;

    int center = (left+right)/2;

    if(left==right){

        //递归出口

        return a[left]>0?a[left]:0;

    }else{

        //出现在两边

        l_max = maxsub(left,center);

        r_max = maxsub(center+1,right);

        //出现在两段之间 从中间往两边求最大

        //左边

        for(int i = center;i>=left;i--){

            sum+=a[i];

            if(sum>l_sum)

                l_sum=sum;

        }

        //右边

        sum=0;

        for(int i = center+1;i<=right;i++){

            sum+=a[i];

            if(sum>r_sum)

                r_sum=sum;

        }

        max = l_sum+r_sum;

        if(l_max>max)

            max = l_max;

        if(r_max>max)

            max = r_max;

        return max;

    }

}

 

2.控制台结果

2.png

m数组看71->33->74->87->46->23->27->72->118->83->130->175->173->203->167->159->200->229->274->289->242->276->319->336->361->385->374->389->356->376->329->306->260->219->251->270->251->296->249->242->230->256->285->253->251->245->259->279->304->281->298->313->279->240->239->284->268->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276->276,该最大值发生在a[26],m[i]<a[i]分支执行0次,则前段数据未发生抛弃,则最大子段和为sum(0,26)

 

总结分析

      用DP求解该问题需要一步步分析,得出递推式是关键。上题中通过穷举和分治不难推算出DP递推式为m[i]=max{m[i-1]+a[i],a[i]},所以分析这类问题先从简单的穷举和分治入手,一步一步减少可节省的计算。


二维码加载中...
本文作者:StanWind      文章标题: 对最大子段和算法的实例评述
本文地址:https://www.stanwind.com/post/71
版权声明:若无注明,本文皆为“Make it Better”原创,转载请保留文章出处。

返回顶部    首页    手机版本    后花园  
版权所有:Make it Better    站长: StanWind    赣ICP备17014296号