`
Simone_chou
  • 浏览: 182758 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

最大连续子序列和

 
阅读更多

1.起点与终点未知,求整个序列的最大子序列和:

    int i;
    maxSum = a[0];
    /* 开始循环求子序列和 */
    for (i = 0; i < len; i++)
    {
        curSum = curSum + a[i];
        /* 与最大子序列和比较,更新最大子序列和 */
        if (curSum > maxSum)   maxSum = curSum;
        /* 动态规划部分,舍弃当前和为负的子序列 */
        if (curSum < 0)    curSum = 0;
    }
    printf("%d\n",maxSum);

2.含右边界的最大子序列和(就是说已知终点从后往前找和的最大值):

    int i;
    int sum = 0;
    int maxSum = a[right];
    for (i = right; i >= left; i--)
    {
        sum += a[i];
        if (sum > maxSum)   maxSum = sum;
    }
        printf("%d\n",maxSum);

3.从含左边界的最大子序列和(就是说已知起点从前往后找和的最大值):

    int i;
    int sum = 0;
    int maxSum = a[left];
    for (i = left; i <= right; i++)
    {
        sum += a[i];
        if (sum > maxSum)
        {
            maxSum = sum;
        }
    }
    printf("%d\n",maxSum);

 

    注意:

    以上总结与F题稍有不同,注意到开头maxsum的赋值,上面的全部算最大子序列和的解法都初始值为第一个元素的值,但是F题初始值为0。因为F题在于算出一个最大连续的正数和出来,如果找不到就默认为0,上面解法是默认为第一项。

 

NYOJ:

 44-子串和:

#include<stdio.h>
int main()
{
	int N,sum,max,number,M;
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d",&M);
		scanf("%d",&number);
		sum=number;
		max=number; 
//初始值默认为第一项,不是0,说明最大子串和可以为负数
		M--;
		while(M--)
		{
			scanf("%d",&number);
			if(sum<0) sum=number;
//动态规划部分,小于0则舍去前面
//不应该是判断下一个number该加不加,number是必须要加的数
//有两种可能,要不就是前面积累了连续的几个数到这个number数时继续积累,要不就是前面的不要,从他开始积累
//总言而知,number要不是它被积累(sum>0的时候),要不就是它积累其他数(sum<0的时候)
			else sum+=number;
			if(sum>max) max=sum;
		}
		printf("%d\n",max);
    }
    return 0;
}

   这题与F题有点区别。

 

F题中的错误:

i=0;  
while(number[i]<0) i++;  
//先忽略前面的负数项,从正数项开始求  
for(i;i<N;i++)  
{  
 sum1+=number[i];  
 if(sum1>max) max=sum1;  
}  

 如果这样写的话,那么就已经规定了从第一个非负数开始向后加和了。

 如果存在序列-1,-2,2,3,-5,-6,10000,-7,-8

 那么如果按照这样写的话(本质就是3的写法),最大子序列和就为9994,

 但是实质上起点应该是不确定的,最大子序列应该是10000才对(本质就是1的写法)。

 所以F题出现了错误按照这个序列的话输出的正确答案应该是10024

 但是如果按照上面这个写法的话就是10012,从而验证出这个的写法在F题是不成立的。

 

动态规划求最大连续子序列和:

     定义max[x]为包含a[x]的序列(a[1],...,a[x])的最大子序列的和,则    max[x+1]=  max[x]>0?max[x]+a[x+1]:a[x+1];

     下面分析max[x+1] = max[x]>0?max[x]+a[x+1]:a[x+1]:

     首先要明白,无论是否要加上max[x],在max[x+1]中,a[x+1]是一定要加上的;若max[x]<0,则无论a[x+1]大于零还是小于零max[x]+a[x+1]<a[x+1],所以,出于该原因,当max[x]<0时,max[x+1]=a[x+1];而若max[x]>0,则无论a[x+1]是大于零还是小于零,均有max[x]+a[x+1]>a[x+1];所以,若为该种情况,max[x+1]=max[x]+a[x+1](注意:再次提醒,a[x+1]是一定要加上的,所以判断是否小于0应该是判断max[i]而不是a[x+1])。

 

F题动态规划解法:

#include<stdio.h>
int number[100005];
int max[100005];
int main()
{
	int N,i,m,sum=0;
	scanf("%d",&N);
	for(i=0;i<N;i++)
	  {
	   scanf("%d",&number[i]);
       sum+=number[i];
	  }

	max[0]=number[0];
	m=0;//一开始只能初始化为0
//如果不初始化为0,而是初始化为max[0]的话
//当序列为-1,-2,-3的时候,最大一直为-1,最后输出的结果是4而不是6了
	for(i=1;i<N;i++)
	{
	 max[i]=max[i-1]>=0?max[i-1]+number[i]:number[i];
	 if(max[i]>m) m=max[i]; //该处存在盲点,第一项没对比到,即max[0]
	}
	if(max[0]>m)  m=max[0];  //另外比完后再对比一次第一项
//测试
//	printf("\n");
//	for(i=0;i<N;i++)
//	 printf("%d ",max[i]);
//	 printf("\n");
	 
	printf("%d\n",2*m-sum);
	return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics