Chinaunix首页 | 论坛 | 博客
  • 博客访问: 168145
  • 博文数量: 33
  • 博客积分: 2015
  • 博客等级: 大尉
  • 技术积分: 317
  • 用 户 组: 普通用户
  • 注册时间: 2009-12-15 17:01
文章分类

全部博文(33)

文章存档

2010年(23)

2009年(10)

我的朋友

分类: C/C++

2010-02-21 01:05:21

问题:

  给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0,依此定义,所求的最优值为:
 
    Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
    例如,当(a1,a2,a3,a4,a4,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为20。
 
 问题求解:
 

/*分治法:
**将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况:
**(1)a[1n]的最大子段和与a[1n/2]的最大子段和相同
**(2)a[1n]的最大子段和与a[n/2n]的最大子段和相同
**(3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n
**T(n)=2T(n/2)+O(n)
**T(n)=O(nlogn)
*/

int MaxSum_DIV(int *v,int l,int r)
{
    int k,sum=0;
    if(l==r)
        return v[l]>=0?v[l]:0;
    else
    {
        int center=(l+r)/2;
        int lsum=MaxSum_DIV(v,l,center);
        int rsum=MaxSum_DIV(v,center+1,r);

        int s1=0;
        int lefts=0;
        for (k=center;k>=l;k--)
        {
            lefts+=v[k];
            if(lefts>s1)
                s1=lefts;
        }

        int s2=0;
        int rights=0;
        for (k=center+1;k<=r;k++)
        {
            rights+=v[k];
            if(rights>s2)
                s2=rights;
        }
        sum=s1+s2;
        if(sum<lsum)
            sum=lsum;
        if(sum<rsum)
            sum=rsum;
    }
    return sum;
}
/*动态规划算法:
**b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j],1<=j<=n。
**由b[j]的定义可易知,当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。故b[j]的动态规划递归式为:
**b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n。
**T(n)=O(n)
*/

int MaxSum_DYN(int *v,int n)
{
    int sum=0,b=0;
    int i;
    for (i=1;i<=n;i++)
    {
        if(b>0)
            b+=v[i];
        else
            b=v[i];
        if(b>sum)
            sum=b;
    }
    return sum;
}

现在回到我们的最初的最大子矩阵的问题,这个问题与上面所提到的最大子段和有什么联系呢?
   假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵,如下所示(ari表示a[r][i],假设数组下标从1开始):
  | a11 …… a1i ……a1j ……a1n |
  | a21 …… a2i ……a2j ……a2n |
  |  .     .     .     .     .     |
  |  .     .     .     .     .     |
  | ar1 …… ari ……arj ……arn |
  |  .     .     .     .     .     |
  |  .     .     .     .     .     |
  | ak1 …… aki ……akj ……akn |
  |  .     .     .     .     .     |
  | an1 …… ani ……anj ……ann |

 那么我们将从第r行到第k行的每一行中相同列的加起来,可以得到一个一维数组如下:
 (ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
 由此我们可以看出最后所求的就是此一维数组的最大子段和问题,到此我们已经将问题转化为上面的已经解决了的问题了。

阅读(2465) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~