c语言求一个整数集合的各个子集的数字和并比较大小，列出和最大的子集

Question

数组里的数字由用户输入
例如输入的数组为1,-2,3,10,-4,7,2，-5，和最大的子数组为3,10，-4,7,2，因此输出的该子数组的和为18

Answer 1

这是个经典算法：

#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; 
}

 结果：