2 u014532847 u014532847 于 2015.06.07 13:37 提问

最大字段和问题动态规划的问题?

int max_sum(int a[],int n,int *best_i,int *best_j)
{
int i,j; // i,j 表示当前子段的起点和终点下标
int this_sum[100];
int sum[100];
int max=0;
this_sum[0]=0;
sum[0]=0;
*best_i=0;// *best_i表示最大子段和的起始下标
*best_j=0;// *best_j表示最大子段和的终点下标
i=1;
for(j=1;j<=n;j++)
{
if(this_sum[j-1]>=0) //判断是否为负数
this_sum[j]=this_sum[j-1]+a[j];
else
{
this_sum[j]=a[j];
i=j;
}

    //如果子段和数组前一个大于下一个元素

    if(this_sum[j]<=sum[j-1])
        sum[j]=sum[j-1];      //对当前子段和赋值
    else
    {
        sum[j]=this_sum[j];
        *best_i=i;
        *best_j=j;
        max=sum[j];
    }

}
return max;

}

if(this_sum[j-1]>=0)   //判断是否为负数
        this_sum[j]=this_sum[j-1]+a[j];//这句代码什么意思?
    else
    {
        this_sum[j]=a[j];
        i=j;
    }

1个回答

caozhy
caozhy   Ds   Rxr 2015.06.07 13:52

http://blog.163.com/zhe_wang_2009/blog/static/172282121201192525042964/

                         { b(j - 1) + a(j)                     当b(j-1) >= 0 //this_sum[j]=this_sum[j-1]+a[j];
              b(j) = {
                        {a(j)                                      当b(j-1) < 0 //this_sum[j]=a[j];
Csdn user default icon
上传中...
上传图片
插入图片