首页 > 其他 > 详细

最大子段和

时间:2017-04-11 10:11:37      阅读:185      评论:0      收藏:0      [点我收藏+]

问题

给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列的子段和的最大值。当所有和为负整数时定义其最大子段和为0。
例如,当(a1,a2,a3,a4,a5,a6)={-2,11,-4,13,-5,-2}时,最大子段和为20。

【算法分析】

技术分享

 

源代码

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

 

最大子段和

原文:http://www.cnblogs.com/wxgblog/p/zuidaziduanhe.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!