Question

最大子数组求解 c++

#include<iostream>
using namespace std;
void MaxSubSum(int *arry,int length);//线性时间算法求子数组最大和，联机算法。
int main(){
int a[]={0,2,4,-8,5,2,-1,2,-4,3};
MaxSubSum(a,10);
return 0;
}
void MaxSubSum(int *arry,int length)
{
int * head=arry;
int * end=arry;
int i,maxsum=0,cursum=0;
for(i=0;i<length;i++)
{
cursum+=arry[i];
if(cursum>maxsum)
{
maxsum = cursum;
end = &arry[i]; //end端点比较好确定 ， head端点如何确定？
}
if(cursum<0)
{
cursum = 0;

}
}
cout<<"最大子数组为:";
while(head<=end)
{
cout<<*head<<" ";
head++;
}
cout<<"\n和为："<<maxsum;
}

想输出最大子数组的每个数。 但head指针想不到怎么确定。 各位大神给点建议

Answer 1

有一个想法 你可以试一下

由于maxsum是根据cursum来变的 所以head在计算cursum的时候就需要确定下来

而cursum又不一定是要求的 所以需要多一个变量保存cursum的head

于是代码改成

void MaxSubSum(int *arry,int length) 
{
    int * head=arry;
	    int * end=arry;
	    int * cur_head = arry;
	    int i,maxsum=0,cursum=0;
	for(i=0;i<length;i++)
	{
		    cursum+=arry[i];
		    if(cursum>maxsum)             
		    {
			        maxsum = cursum;
			        end = &arry[i];        //end端点比较好确定 ， head端点如何确定？ 
			        head = cur_head;
		    }    	
		    if(cursum<0)
		    {
			        cursum = 0;
			        cur_head = &array[i];
	
		    }	
	}
	    cout<<"最大子数组为:";
	while(head<=end)
	{
		cout<<*head<<"  ";
		head++;
	}
	cout<<"\n和为："<<maxsum;
}

不过个人认为你这个求最大的算法本身就有问题

应该改成

void MaxSubSum(int *arry,int length) 
{
    int * head=arry;
	    int * end=arry;
	    int * cur_head = arry;
	    int i,maxsum=0x80000000,cursum=0;
	for(i=0;i<length;i++)
	{
    	    if(curSum <= 0)  
    	    {
                curSum = data[i];  
                cur_head=&data[i];
            }
            else  
                curSum += data[i];  
              
            if(curSum > sum)  
            {
                sum = curSum;  
                head = cur_head;
                end=&data[i];
            }
	}
	    cout<<"最大子数组为:";
	while(head<=end)
	{
		cout<<*head<<"  ";
		head++;
	}
	cout<<"\n和为："<<maxsum;
}

你可以试试 

追问

没看出你所说的改算法是在哪改了。 其次{1,2,3,4,5，-16，17}发生越界问题。

追答

完整程序：

#include<iostream>
using namespace std;
void MaxSubSum(int *arry,int length);//线性时间算法求子数组最大和，联机算法。 
int main(){
int a[]={1,2,3,4,5,-16,17};
MaxSubSum(a,sizeof a / sizeof(int));
return 0;
}
void MaxSubSum(int *arry,int length) 
{
    int * head=arry;
    int * end=arry;
    int * cur_head = arry;
    int i,maxsum=0x80000000,curSum=0;
for(i=0;i<length;i++)
{
         if(curSum <= 0)  
         {
                curSum = arry[i];  
                cur_head=&arry[i];
            }
            else  
                curSum += arry[i];  
              
            if(curSum > maxsum)  
            {
                maxsum = curSum;  
                head = cur_head;
                end=&arry[i];
            }
}
    cout<<"最大子数组为:";
while(head<=end)
{
cout<<*head<<"  ";
head++;
}
cout<<"\n和为："<<maxsum;
}

追问

算法该了哪呢？

追答

1,2,3,4,5，-16,17 你算一下全加起来是多少 是16啊

1,2,3,4,5，-16,17，-2 这个你怎么加能加出来18来？

1+2+3+4+5=15 不是17

初始值maxsum 设置为0的话 如果全数列为负值 会出错
其他的关系不是很大 换个写法而已

Answer 2

你最好是先搞明白你这个程序的算法，不确定这个算法基础，代码就无法确定

追问

呵呵，，，，

追答

if(cursum<0)
{
head=&arry[i+1]; //head 应该是i+1 
cursum = 0;
}

追问

这里设head有用吗？ 假如一个数组是{1,2,3,4,5，-16}。自己想想照你这样设head会怎样。能不能得到正确答案不说，光是数组越界的问题都没注意。

追答

那是你代码的BUG，所以我说，如果你读不懂算法，就解决不了问题！

试一下，如下代码
void MaxSubSum1(int *arry,int length) 
{
    int * head=arry;
int * end=arry;
int i,maxsum=*arry,cursum=*arry;
//以上初值，都是假定，第一个元素就是构成的最大子数组

for(i=1;i<length;i++)
{
if(cursum<0)
{
head=&arry[i]; //head 应该是i 
cursum = arry[i];
}
else
{
cursum+=arry[i];
}

if( cursum>maxsum )             
{
maxsum = cursum;
end = &arry[i];        //end端点比较确定  head端点何确定 
}    

}
cout<<"数组:";
while(head<=end)
{
cout<<*head<<"  ";
head++;
}
cout<<"\n："<<maxsum;
}

追问

自己好好想想吧 还是原来的那个数组。{1,2,3,4,5，-16} 。亏我还真信了，还详细读了读代码。

追答

我测试正确的啊。好了，不说了。

追问

简直逗我，能跑出来才怪。 head指针都在end指针后面了，你还真能跑出来，膜拜大神。你简直比编译器还NB

追答

程序的确有BUG，但不是你说的内容