求一个数组中最大的相邻元素之和

assiss

1. 
   
2. #include <stdio.h>;
   
3. #include <stdlib.h>;
   
4. 
   
5. void MaxSum(int *m, int n)
   
6. {
   
7.     int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0;
   
8.         max=m[0];
   
9.         for(i=0;i<n && m[i]<=0;i++)//我觉得把负数单独拿出来考虑更好一点
   
10.         {
    
11.                 if(m[i]>;max)
    
12.                 {
    
13.                         max=m[i];
    
14.                         start=i;
    
15.                 }
    
16.         }
    
17.         if(i==n)
    
18.         {
    
19.                 printf("start %d, end %d, sum %d\n", start, start, max);
    
20.                 return;
    
21.         }
    
22.         start2=start=istart=i;
    
23.         for(i=n-1;i >;-1 && m[i]<=0;i--);//末尾的非正数也拿掉,少做几次加法
    
24.         iend=i;
    
25.         max=m[start];
    
26.         sum=0;
    
27.         for(i=istart;i<=iend;i++)
    
28.         {
    
29.                 sum+=m[i];
    
30.                 sum2+=m[i];
    
31.                 if(sum>;max)
    
32.                 {
    
33.                         end=i;
    
34.                         max=sum;
    
35.                 }
    
36.                 if(sum2<=0 && m[i]>;0)//这里用的算法和yuxh的一样.真佩服yuxh,算法这方面做得太好了
    
37.                 {
    
38.                         sum2=m[i];
    
39.                         start2=i;
    
40.                 }
    
41.                 if(sum2>;max)
    
42.                 {
    
43.                         start=start2;
    
44.                         end=i;
    
45.                         max=sum2;
    
46.                 }
    
47.         }
    
48.     printf("start %d, end %d, sum %d\n", start, end, max);
    
49. }
    
50. int main()
    
51. {
    
52.     int m[10] = {-2,-3,-6,-3,-4,-3,-2,-1,-2,-3};
    
53. 
    
54.     MaxSum(m, 10);
    
55.         return 0;
    
56. }
    

复制代码

assiss

原帖由 "yuxh" 发表：
,3,-6,3,4,3,-2,5,2,-3};

start 0, end 8, sum 14

sorry,还没完全领会精神就乱发程序了.       
再来,反正脸皮厚

1. 
   
2. #include <stdio.h>;
   
3. #include <stdlib.h>;
   
4. 
   
5. void MaxSum(int *m, int n)
   
6. {
   
7.     int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0;
   
8.         max=m[0];
   
9.         for(i=0;i<n && m[i]<=0;i++)
   
10.         {
    
11.                 if(m[i]>;max)
    
12.                 {
    
13.                         max=m[i];
    
14.                         start=i;
    
15.                 }
    
16.         }
    
17.         if(i==n)
    
18.         {
    
19.                 printf("start %d, end %d, sum %d\n", start, start, max);
    
20.                 return;
    
21.         }
    
22.         end=start2=start=istart=i;//加了个END.因为发现如果只有一个正数时END有误.
    
23.         for(i=n-1;i >;-1 && m[i]<=0;i--);
    
24.         iend=i;
    
25.         sum2=sum=max=m[start];
    
26.         for(i=istart+1;i<=iend;i++)
    
27.         {
    
28.                 sum+=m[i];
    
29.                 sum2+=m[i];
    
30.                 if(sum>;max)
    
31.                 {
    
32.                         end=i;
    
33.                         max=sum;
    
34.                 }
    
35.                 if(m[i-1]<=0 && m[i]>;0)
    
36.                 {
    
37.                         sum2=m[i];
    
38.                         start2=i;
    
39.                 }
    
40.                 if(sum2>;max)
    
41.                 {
    
42.                         start=start2;
    
43.                         end=i;
    
44.                         sum=max=sum2;//这里又修改了.唉.惭愧.
    
45.                 }
    
46.         }
    
47.     printf("start %d, end %d, sum %d\n", start, end, max);
    
48. }
    
49. int main()
    
50. {
    
51.     int m[10] = {2, 3, -6, 3, 4, 3, -2, 5, 2, -3};
    
52. 
    
53.     MaxSum(m, 10);
    
54.         return 0;
    
55. }
    

复制代码

assiss

原帖由 "yuxh" 发表：
, 3, -6, 3, 4, 3, -7, 5, 3, -3};
start 3, end 5, sum 10

已经改了.嘿嘿.这次速度比你快一点.刚贴出来就看到错了......不过你F5的速度也太快了吧???

assiss

原帖由 "yuxh" 发表：
F5是啥东西？
我看你们两个的程序看得累死
    

习惯上把刷新说成"F5",呵呵,当年用IE落下的毛病.
我第一次贴出修改的程序,里面有你说的问题.但我在很短的时间内就修改了,竟然还是让你看到了,嘿嘿,所以说你的F5速度很快.
你的算法功底太强了,怎么学的?我现在设计算法,总会出错,然后一点一点修改,最后得到一个也不知道是不是正确的结果.不知道是不是因为太懒了,不肯从数学角度上考虑这个问题.

assiss

原帖由 "yuxh" 发表：
偶以前数学系的，大学里就学过BASIC
对于复杂一点的问题先在纸上列一下，把数学问题先搞清楚，不要急着写程序，不然出了问题也不知道什么问题，一点一点地改，把别人看出来的问题补掉，但也不明白最后还会不会出问�.........

受益匪浅啊.数学系出来的就是不一样.做程序果然很有前途.

assiss

老天啊,yuxh是不是还准备把程序简化到一两行?受不了了,很受伤,很受打击.aero,借个肩膀用一下.哇哇哇................

assiss

怎么可能啊。骗小孩的，guile也相信？

assiss

顶起来。有朋友要。找得好苦。