算法最大子阵和

算法第十八周作业最大子阵和

主要参考：http://t.csdn.cn/osKRP

最大子段和

对于最大子矩阵和的问题，我们从简单的想起，假设这个最大子矩阵的维数是一维，要找出最大子矩阵, 原理与求“最大子段和问题” 是一样的。

摘自百度百科：最大子段和_百度百科

问题： 给定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 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)时，最大子段和为20。

分治法

算法描述如下

针对最大子段和这个具体问题本身的结构，我们还可以从算法设计的策略上对上述O(n^2)计算时间算法进行更进一步的改进。从问题的解结构也可以看出，它适合于用分治法求解。

如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种情况：

（1） a[1:n]的最大子段和与a[1:n/2]的最大子段和相同

（2） a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同

（3） a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。

对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，并在a[n/2+1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。据此可以设计出最大子段和问题的分治算法如下：

#include<stdio.h>
#define MAX 100
int maxsub(int left,int right);
int a[MAX];
int main()
{
    int i,count;
    scanf("%d",&count);
    for(i=0;i<count;i++)
        scanf("%d",&a[i]);
    printf("%d\n",maxsub(0,count-1));
    return 0;
}
int maxsub(int left,int right)
{
    int center,i,sum,left_sum,right_sum,left_max,right_max;
    center=(left+right)>>1;
    if(left==right)
        return a[left]>0?a[left]:0;
    else
    {
        left_sum=maxsub(left,center);
        right_sum=maxsub(center+1,right);
        sum=0;
        left_max=0;
        for(i=center;i>=left;i--)
        {
            sum+=a[i];
            if(sum>left_max)
                left_max=sum;
        }
        sum=0;
        right_max=0;
        for(i=center+1;i<=right;i++)
        {
            sum+=a[i];
            if(sum>right_max)
                right_max=sum;
        }
        sum=right_max+left_max;
        if(sum<left_sum)
            sum=left_sum;
        if(sum<right_sum)
            sum=right_sum;
    }
    return sum;
}

递推法

在对于上述分治算法的分析中我们注意到，若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且i<=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。

代码如下：

#include <stdlib.h>
#include<stdio.h>
int main()
{
    int count;
    int a[100];
    int b[100];
    int i;
    int max;
    scanf("%d",&count);
    for(i=0; i<count; i++)
    {
        scanf("%d",&a[i]);
    }
    b[0]=a[0];
    max=b[0];
    for(i=1; i<count; i++)
    {
        if(b[i-1]>0)
            b[i]=b[i-1]+a[i];
        else
            b[i]=a[i];
        if(b[i]>max)
            max=b[i];
    }
    printf("%d\n",max);
    return 0;
}

个人评注：

b[i]的意义是包含a[i]在内的位置在i之前的最大子段。

如果b[i-1]<=0，那么b[i]就不用理睬前面的，因为前面的子段不能增大自己的和，也就是前面i-1的部分已经和接下来的最大字串无关了。

这样我们把问题（假设子段长度，也就是段数是n），那么我们把原问题分解为了n个子问题。但是这些子问题并不是相互独立的，而是部分地联系在一起，因此实际上也就用到了动态规划的方法。

每个b[i]都是一个子问题的解，也就是求 包含a[i]在内的位置在i之前的最大子段和 的解。然后我们观察到，b[i]和b[i-1]的关系是b[i]=max(b[i-1]+a[i],a[i])，也就是b[i]和之前是有一定关系的，要想求出b[i]就需要先求出b[i-1]，然后看b[i-1]是否大于0：

• 如果大于0，现在这个字串就要在b[i-1]对应的字串加上a[i]
• 如果小于等于0，就不用管前面的，直接取a[i]

所以b[i]与前面的子问题b[i-1]的关系是动态的，在程序求出b[i-1]之前我们并不确切知道b[i]与b[i-1]的关系。这和比如斐波那契数列不同，对于斐波那契数列，当前所求位置的值与之前所求的值的关系是可以确切知道的，就算我们不知道前面所求的值是什么，也就是a[i]=a[i-1]+a[i-2]。但是，对于b[i]与b[i-1]的关系我们可以划分出几种情况，在不同情况下它们关系我们是可以切确知道的。

实际上动态规划的思想并不难，但是想对具体的问题找出恰当的子问题却十分精妙，需要高超的洞察力和丰富的经验。当然，这些我都没有，但是问题不大。