最大子段和问题（分治）（##）

#include<stdio.h>

#define MAX 100001

struct str
{
int nFrom;
int nTo;
int nSum;
};

str getMax(int nData[],int n);
void vPutOut(str A);
str get3Parts(int nData[],int left,int right);
str getMid(int nData[],int left,int mid,int right);

int main()
{
int nData[MAX];
int i,n;
str A;

scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&nData[i]);
}
A=getMax(nData,n);
vPutOut(A);

return 0;
}

str getMax(int nData[],int n)
{
str B;
B=get3Parts(nData,1,n);
return B;
}

void vPutOut(str A)
{
printf("FROM=%d,TO=%d\n",A.nFrom,A.nTo);
printf("SUM=%d\n",A.nSum);
}

str get3Parts(int nData[],int left,int right)
{
str B;
str Bleft,Bright,Bmid;

int from,to,mid;
int nSum,leftSum,rigthSum,midSum;

nSum=0;
left=0;
right=0;

if(left==right)
{
if(nData[left]>0)
{
from=left;
to=left;
nSum=nData[left];
}
}
else
{
mid=(left+right)/2;
Bleft=get3Parts(nData,left,mid);
leftSum=Bleft.nSum;
Bright=get3Parts(nData,mid+1,right);
rigthSum=Bright.nSum;
Bmid=getMid(nData,left,mid,right);
midSum=Bmid.nSum;


if((leftSum>rigthSum)&&(leftSum>midSum))
{
nSum=leftSum;
from=Bleft.nFrom;
to=Bleft.nTo;
}
else
{
if(rigthSum>midSum)
{
nSum=rigthSum;
from=Bright.nFrom;
to=Bright.nTo;
}
else
{
nSum=midSum;
from=Bmid.nFrom;
to=Bmid.nTo;
}
}
}
B.nSum=nSum;
B.nFrom=from;
B.nTo=to;

return B;
}

str getMid(int nData[],int left,int mid,int right)
{
str B;
int from,to;
int nSum,s1,s2;
int i;

from=mid;
to=mid;
nSum=0;
s1=0;

for(i=mid;i<=left;i--)
{
nSum+=nData[i];

if(nSum>s1)
{
s1=nSum;
from=i;
}
}

nSum=0;
s2=0;

for(i=mid;i<=right;i++)
{
nSum+=nData[i];

if(nSum>s2)
{
s2=nSum;
to=i;
}
}

nSum=s1+s2;
B.nFrom=from;
B.nTo=to;
B.nSum=nSum;

return B;
}