分治法求最大序列和 - 编程论坛

程序老是运行不了，搞了好久才发现是DivideAndConquer(int Left,int Right,int Array[])里的Left，Right首字母没有大写。

这个递归很难将函数运行的过程写出来吧，假设DivideAndConquer函数是正确的接着写就好。我是这样理解这里的递归的，有其他看法的么？

DivideAndConquer函数是否可以放在求跨边界最大子列和后面，这个我试了一下，试了几组可以的，先求跨边界再求两边的方法本就是对的吧。
如果我要输出最大序列和的序列号是从哪到哪的怎么输出？这个我还没想，不会。

程序代码：

#include <stdio.h>

int Compare(int LeftMaxArray , int RightMaxArray , int MaxCrossBorderArray )
{
    int Max=LeftMaxArray;
    if( Max < RightMaxArray )
    {
        Max = RightMaxArray;
    }

    if(Max < MaxCrossBorderArray )
    {
        Max = MaxCrossBorderArray;
    }

    return Max;
}

int DivideAndConquer(int Left,int Right,int Array[])
{
    int LeftMaxArray , RightMaxArray ;            //左右两边序列和最大值
    int LeftCrossBorderArray , RightCrossBorderArray ;
    int LeftMaxCrossBorderArray , RightMaxCrossBorderArray , MaxCrossBorderArray ;  //跨边界序列和最大值
    int MaxArray;
    int i,Mid;

    if(Left==Right) //分治法求解的递归出口
    {
        if(Array[Left>0])    return Array[Left];
        else return 0;
    }

    //用分治法递归的求解左右两边子序列和最大值
    Mid=( Left + Right ) / 2;

    LeftMaxArray = DivideAndConquer(Left , Mid , Array);
    RightMaxArray = DivideAndConquer(Mid+1 , Right , Array);

    //求跨边界序列和最大值
    LeftMaxCrossBorderArray = -9999; RightMaxCrossBorderArray = -9999;
    LeftCrossBorderArray=0 ; RightCrossBorderArray=0 ;

    for(i=Mid ; i>=Left ; i--)   //从中间向左扫描
    {
        LeftCrossBorderArray+= Array[i] ;
        if( LeftCrossBorderArray > LeftMaxCrossBorderArray )
            LeftMaxCrossBorderArray = LeftCrossBorderArray ;
    }

    for(i=Mid+1 ; i<=Right ; i++)    //从中间向右扫描
    {
        RightCrossBorderArray+= Array[i] ;
        if( RightCrossBorderArray > RightMaxCrossBorderArray )
            RightMaxCrossBorderArray = RightCrossBorderArray ;
    }
    MaxCrossBorderArray = LeftMaxCrossBorderArray + RightMaxCrossBorderArray ;

    //比较左右两边序列最大和与跨边界序列最大和
    MaxArray=Compare( LeftMaxArray , RightMaxArray ,  MaxCrossBorderArray) ;

    return MaxArray;

}

int main()
{
    int Array[100000];
    int i,k;
    int MaxArray;

    scanf("%d",&k);

    for(i=0;i<k;i++)
        scanf("%d",&Array[i]);

    MaxArray = DivideAndConquer( 0 , k-1 , Array );

    printf("%d\n", MaxArray );

    return 0;

};