最大子数组

#include <stdio.h>//显示数组信息voidshowArray(intarray[], intlen);
//求和intadd(intarray[], intstart, intend);
intmax(intarray[], intstart, intend);
intmix(intarray[], intstart, intend);
intmain(void)
{
//原始数组intarray1[] = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97}, len=17, sum=0, start=0, end=0;
showArray(array1, len);
//方法1：根据原始数组，遍历找出差价最高的一对for (inti=0; i<len; i++)
    {
for (intj=i+1; j<len; j++)
        {
if (sum< (array1[j] -array1[i]))
            {
sum=array1[j] -array1[i];
start=i;
end=j;
            }
        }
    }
printf("The start postion is %d,end postion is %d,sum is %d\n", start, end, sum);
//初始化start=0;
end=0;
sum=0;
//差价数组intarray2[] = {0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
showArray(array2, len);
//方法2：根据差价数组，遍历找出加和最高的一对for (inti=1; i<len; i++)
    {
intj=0;
while (j+i<len)
        {
if (sum<add(array2, j, j+i))
            {
sum=add(array2, j, j+i);
start=j;
end=j+i;
            }
j++;
        }
    }
printf("The start postion is %d,end postion is %d,sum is %d\n", start, end, sum);
showArray(array2, 16);
sum=max(array2, 0, 16);
printf("sum is %d\n", sum);
}
voidshowArray(intarray[], intlen)
{
for (inti=0; i<len; i++)
    {
printf("%5d", array[i]);
    }
printf("\n");
}
intadd(intarray[], intstart, intend)
{
intsum=0;
for (inti=start; i<=end; i++)
    {
sum+=array[i];
    }
returnsum;
}
intmix(intarray[], intstart, intend)
{
}
intmax(intarray[], intstart, intend)
{
if (start==end)
    {
returnarray[start];
    }
intlstart=start, lend= (start+end) /2, rstart=lend+1, rend=end, lmax=0, mmax=0, rmax=0, mstart=0, mend=0;
for (inti=lend; i>=0; i--)
    {
if (lmax<add(array, i, lend))
        {
lmax=add(array, i, lend);
mstart=i;
        }
    }
for (intj=rstart; j<=rend; j++)
    {
if (rmax<add(array, rstart, j))
        {
rmax=add(array, rstart, j);
mend=j;
        }
    }
mmax=add(array, mstart, mend);
lmax=mmax>max(array, rstart, rend) ?mmax : max(array, rstart, rend);
rmax=mmax>max(array, rstart, rend) ?mmax : max(array, rstart, rend);
returnlmax>rmax?lmax : rmax;
}
代码段2：#include <stdio.h>structsubary{
intstart, end, sum;
};
//显示数组信息voidshowArray(intarray[], intlen);
//求和intadd(intarray[], intstart, intend);
structsubarymax(intarray[], intstart, intend);
intmain(void)
{
//差价数组intarray2[] = {0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}, len=17;
showArray(array2, len);
structsubaryresult=max(array2, 0, 16);
printf("The start position is %d,end positioni is %d,sum is %d", result.start, result.end, result.sum);
}
voidshowArray(intarray[], intlen)
{
for (inti=0; i<len; i++)
    {
printf("%5d", array[i]);
    }
printf("\n");
}
intadd(intarray[], intstart, intend)
{
intsum=0;
for (inti=start; i<=end; i++)
    {
sum+=array[i];
    }
returnsum;
}
structsubarymax(intarray[], intstart, intend)
{
if (start==end)
    {
structsubaryresult;
result.start=start;
result.end=end;
result.sum=add(array, start, end);
returnresult;
    }
intlstart=start, lend= (start+end) /2, rstart=lend+1, rend=end, lmax=0, mmax=0, rmax=0, mstart=0, mend=0;
structsubarylsub, msub, rsub;
for (inti=lend; i>=0; i--)
    {
if (lmax<add(array, i, lend))
        {
lmax=add(array, i, lend);
mstart=i;
        }
    }
for (intj=rstart; j<=rend; j++)
    {
if (rmax<add(array, rstart, j))
        {
rmax=add(array, rstart, j);
mend=j;
        }
    }
msub.start=mstart;
msub.end=mend;
msub.sum=add(array, mstart, mend);
lsub=msub.sum>max(array, lstart, lend).sum?msub : max(array, lstart, lend);
//lsub = max(array, lstart, lend);rsub=msub.sum>max(array, rstart, rend).sum?msub : max(array, rstart, rend);
//rsub = max(array, rstart, rend);//result = msub.sum > lsub.sum ? msub : lsub;returnlsub.sum>rsub.sum?lsub : rsub;
}