| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1289 人关注过本帖
标题:请教个问题,关于最大子序列求和问题
只看楼主 加入收藏
xilixjd
Rank: 1
等 级:新手上路
帖 子:11
专家分:9
注 册:2015-12-6
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
请教个问题,关于最大子序列求和问题
程序代码:
//Code By Pnig0s1992  
//Date:2012,3,12  
#include <stdio.h>  
#include <Windows.h>  
#include <stdlib.h>  
  
#define N 8  
  
int CallSubsequenceSum(int s[],int iLength);  
int SubsequenceSum(int s[],int iLeft,int iRight);  
int Maxinthree(int a,int b,int c);  
  
int main(int argc,CHAR * argv[])  
{  
    int myList[N] = {4,-3,5,-2,-1,2,6,-2};  
    int myResult;  
    for(int i=0;i<N;i++)  
    {  
        printf("%d ",myList[i]);  
    }  
    myResult = CallSubsequenceSum(myList,N-1);  
    printf("\n最大子序列和为:%d",myResult);  
    system("pause");  
}  
  
int CallSubsequenceSum(int s[],int iLength)  
{  
     return SubsequenceSum(s,0,iLength);  
}  
  
int SubsequenceSum(int s[],int iLeft,int iRight)  
{  
    int iMaxLeftSum,iMaxRightSum; //表示  
    int iRightBorderSum = 0,iLeftBorderSum = 0;  
    int iMaxLeftBorderSum = 0,iMaxRightBorderSum = 0;  
    int iCenter;  
    if(iLeft == iRight) //解决小容量情况,当序列只有一个元素时,非负则返回唯一值,否则返回0(基准情况)  
    {  
        if(s[iLeft]>0)  
        {  
            return s[iLeft];  
        }else 
        {  
            return 0;  
        }  
    }  
    iCenter = (iLeft+iRight)/2;  
    iMaxLeftSum = SubsequenceSum(s,iLeft,iCenter); //每次递归返回时,该值为该子段的最终左最大子序列和  ?
    iMaxRightSum = SubsequenceSum(s,iCenter+1,iRight); //每次递归返回时,该值为该子段的右最大自序列和  ?
    for(int i=iCenter;i>=iLeft;i--) //从中间向左扩展求子段的最大子序列和,必然包括子段的最右端数  
    {  
        iLeftBorderSum+=s[i];  
        if(iLeftBorderSum>iMaxLeftBorderSum)  
        {  
            iMaxLeftBorderSum = iLeftBorderSum; //包含左端数的最大子序列和  ?
        }  
    }  
    for(int j=iCenter+1;j<=iRight;j++) //从中间向右扩展求子段的最大子序列和,必然包括子段的最左端数  
    {  
        iRightBorderSum += s[j];  
        if(iRightBorderSum > iMaxRightBorderSum)  
        {  
            iMaxRightBorderSum = iRightBorderSum; //包含右端数的最大子序列和  ?
        }  
    }  
    //返回左子最大序列和,右最大子序列,及横跨中间的最大子序列和三者的最大值  
    return Maxinthree(iMaxLeftSum,iMaxRightSum,iMaxLeftBorderSum+iMaxRightBorderSum);   
}  
  
int Maxinthree(int a,int b,int c)  
{  
    if(b>a)  
        a=b;  
    if(a<c)  
        return c;  
    else 
        return a;  
} 

打问号的是没弄懂的地方,分别是第48、49行的递归为什么能实现左边、右边的最大子序列,为什么我觉得是左边第一个元素,右边的第一个元素。
还有第55行、63行,为什么包含了左端数、右端数的最大子序列和,我觉得if语句一用,就把最大子序列给存起来了,并不包含两端的数啊。

[此贴子已经被作者于2015-12-15 18:42编辑过]

搜索更多相关主题的帖子: color include 
2015-12-15 18:41
xilixjd
Rank: 1
等 级:新手上路
帖 子:11
专家分:9
注 册:2015-12-6
收藏
得分:0 
2015-12-15 22:07
kehanping
Rank: 2
等 级:论坛游民
威 望:1
帖 子:25
专家分:88
注 册:2015-12-10
收藏
得分:7 
程序没有问题啊,
iMaxLeftSum = SubsequenceSum(s,iLeft,iCenter); //每次递归返回时,该值为该子段的最终左最大子序列和  
iLeft=0,所以包含了最左边的数;
    iMaxRightSum = SubsequenceSum(s,iCenter+1,iRight); //每次递归返回时,该值为该子段的右最大自序列和  
iRight=N-1,所以保含了最右边的数。
if语句的作用其实就是保留最大和。每递归一次,如果s[i]或者s[j]都是正数的话,都会变大(只是你这个序列有负数,所以当有某一次递归s[i]或者s[j]为负数的时候,不变)
2015-12-15 22:21
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:7 
什么叫“最大子序列求和”?
难道是求一个 连续的子序列,且此子序列的和最大?

我随手写一个,没验证,仅供参考
程序代码:
#include <stdio.h>

int main( void )
{ 

    int s[] = { 4,-3,5,-2,-1,2,6,-2 };

    int maxsum = 0;
    int cursum = 0;
    for( size_t i=0; i!=sizeof(s)/sizeof(*s); ++i )
    {
        if( cursum+s[i] > 0 )
        {
            cursum += s[i];
            if( maxsum < cursum )
                maxsum = cursum;
        }
        else
            cursum = 0;
    }
    printf( "maxsum = %d\n", maxsum );

    return 0;
}

2015-12-16 09:28
xilixjd
Rank: 1
等 级:新手上路
帖 子:11
专家分:9
注 册:2015-12-6
收藏
得分:0 
回复 3楼 kehanping
递归能解释一下吗,不知道是怎么得出结果的
2015-12-16 10:53
xilixjd
Rank: 1
等 级:新手上路
帖 子:11
专家分:9
注 册:2015-12-6
收藏
得分:0 
回复 4楼 rjsp
对的,就是这个意思,我是看的书上内容,你这个是最好的算法,我贴出来的是倒数第二种算法也就是二分法。
另外,能解释一下这个递归是怎么得出结果的吗
2015-12-16 10:55
快速回复:请教个问题,关于最大子序列求和问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.038485 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved