这是个经典算法:
#include "stdio.h"
int maxa(int * a,int l,int* s,int* e) /*用s和e 记录子数组起始和终止地址,l是数组长度*/
{
int summax=0; /*最大子数组的和*/
int sumcur=0; /*当前和*/
int i;
*s=0;*e=0;
for(i=0;i<l;i++)
{
sumcur+=a[i];
if(sumcur>summax)
{
summax=sumcur;
*e=i;
}
else if(sumcur<0)
{
sumcur=0;
*s=i+1;
}
}
if(summax<=0)
{
summax=a[0];
for(i=0;i<l;i++)
{
if(summax<a[i])
{
summax=a[i];
*s=i;
*e=i;
}
}
}
return summax;
}
int main()
{
int a[]={1,-2,3,10,-4,7,2,-5};
int start,end;
printf("最大子数组的和为:%d\n",maxa(a,8,&start,&end));
printf("最大子数组的元素下标从%d到%d:\n",start,end);
while(start<=end)
{
printf("%d ",a[start++]);
}
printf("\n");
return 0;
}
结果:
![](https://video.ask-data.xyz/img.php?b=https://iknow-pic.cdn.bcebos.com/91ef76c6a7efce1b4c1c47e8ad51f3deb48f65d9?x-bce-process=image%2Fresize%2Cm_lfit%2Cw_600%2Ch_800%2Climit_1%2Fquality%2Cq_85%2Fformat%2Cf_auto)