該樓層疑似違規已被系統折疊 隐藏此樓檢視此樓
純新手,最近想學一下算法,上網看了個教程,看到了一個很經典的傳回最大子數組之和的問題,然後我想問一下我用分治法把最大和求出來了,但是要怎麼傳回子數組本身呢,因為是函數的遞歸,是以有些雲裡霧裡。以下是我模仿着寫的代碼。輸出結果是30。
int MaxAddSub(int *a,int front,int end)
{ //int i1,i2;
if(front==end)
return a[front];
int Middle=(front+end)/2;//尋找中間位置
int Max_1= MaxAddSub(a,front,Middle);//求左側的數組最大的字首和
int Max_2= MaxAddSub(a,Middle+1,end);//求右側的數組最大的字首和
int i,New=0,Left=0;
for(i=Middle;i>=front;i--)
{
New+=a[i];
if(Left
{
Left=New;
//i1=i;
}
}
int Right=0;
New=0;
for(i=Middle+1;i<=end;i++)
{
New+=a[i];
if(Right
{
Right=New;
//i2=i;
}
}
int Max_3=Left+Right;
if(Max_1>Max_2&&Max_1>Max_3)
return Max_1;
if(Max_2>Max_1&&Max_2>Max_3)
return Max_2;
if(Max_3>Max_2&&Max_3>Max_1)
return Max_3;
int main()
{
int Max;
int a[9]={1,-2,3,10,-4,7,2,5,7};
Max=MaxAddSub(a,0,8);
printf("%d",Max);
return 0;
}