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

guile

我的想法是这样：
1如果全是负数，那么返回值就是最大的那个负数，存到sum
2当遇到正数时，就考虑求和sum1。一直求到最后一个正数，
3但是当后面第二个正数大于后面第一个非正数的绝对值，就把这两个数加到sum1，然后走到第2步。否则，4
4sum1和sum比较，看是否要更改。

代码实现如下

1. 
   
2. #include<iostream>;
   
3. using namespace std;
   
4. 
   
5. void MaxSum(int* ip,int size)
   
6. {
   
7.         int sum=ip[0],sum1=sum,start=0,end=0,start1,end1;
   
8.         int i=0;
   
9. 
   
10.         while(ip[i]<0&&i<size)
    
11.         {
    
12.                 if(ip[i]>;sum)
    
13.                 {
    
14.                         sum=ip[i];
    
15.                         start=end=i;
    
16.                 }
    
17.         }
    
18. 
    
19.         while(i<size)
    
20.         {
    
21.                 if(ip[i]>;0)
    
22.                 {
    
23.                         start1=end1=i;
    
24.                         sum1=0;
    
25.                         while((end1<size)&&(ip[end1]>;0))
    
26.                         {
    
27.                                 sum1+=ip[end1];
    
28.                                 end1++;
    
29.                                 i=end1+1;
    
30.                                 if((ip[end1]<=0)&&(end1<size-1)&&(ip[end1+1]>;-ip[end1]))
    
31.                                 {
    
32.                                         sum1+=ip[end1]+ip[end1+1];
    
33.                                         end1+=2;
    
34.                                 }
    
35.                         }
    
36.                        
    
37.                         if(sum1>;sum)
    
38.                         {
    
39.                                 start=start1;
    
40.                                 end=end1-1;
    
41.                                 sum=sum1;
    
42.                         }
    
43.                 }
    
44.                 else
    
45.                 {
    
46.                         i++;
    
47.                 }
    
48.         }
    
49. 
    
50.         cout<<"Start: "<<start<<endl
    
51.                 <<"End: "<<end<<endl;
    
52.         for(i=start;i<end;i++)
    
53.                 cout<<ip[i]<<" ";
    
54.         cout<<endl
    
55.                 <<"The sum is "<<sum<<endl;
    
56. }
    
57. 
    
58. int main()
    
59. {
    
60.         int a[]={2,3,-6,3,4,3,-2,5,2,-3};
    
61.         MaxSum(a,10);
    
62.         return 0;
    
63. }

复制代码

liulang0808

强

guile

虽然上面的代码看上去循环有嵌套，不过还是O(n)的算法，内循环改变的也是外循环的i
另外i和end1两个变量其实可以合并，不过为了容易阅读一点，还是多用了一个变量

guile

[quote]原帖由 "guile"][/quote 发表：

不行，发现自己第三步考虑太简单了，等我改改

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. }
    

复制代码

guile

算法如下
1用sum,start,end储存最大和，开始下标，结束下标。
如果数组里开始遇到的都是负数，那么sum保存的就是最大的负数

2当遇到正数的时候，开始用sum1求和，start1代表开始下标，end1要用来探测所以存储的是结束下标的下一个
求和一直求到遇到非正数或者结束
如果不是正数，探测下一个下标作为开始

3把后面的非正数和sum1加到sum2，再加下一个正数。
如果sum2>;=sum1，则用sum2替换sum1，回到2
否则4
4比较sum和sum1，sum1大的话替换掉sum，以后的探测下标从end1-1开始

1. #include<iostream>;
   
2. using namespace std;
   
3. 
   
4. void MaxSum(int* ip,int size)
   
5. {
   
6.         int sum=ip[0],sum1,sum2,start=0,end=0,start1,end1;
   
7.         int i=0;
   
8. 
   
9.         while(i<size&&ip[i]<0)
   
10.         {
    
11.                 if(ip[i]>;sum)
    
12.                 {
    
13.                         sum=ip[i];
    
14.                         start=end=i;
    
15.                 }
    
16.                 i++;
    
17.         }
    
18. 
    
19.         while(i<size)
    
20.         {
    
21.                 if(ip[i]>;0)
    
22.                 {
    
23.                         start1=end1=i;
    
24.                         sum1=0;
    
25.                         while((end1<size)&&(ip[end1]>;=0))
    
26.                         {
    
27.                                 sum1+=ip[end1];
    
28.                                 end1++;
    
29.                                 i=end1;
    
30.                                 if((i<size)&&(ip[i]<=0))
    
31.                                 {
    
32.                                         sum2=sum1;
    
33.                                         while((i<size)&&(ip[i]<=0))
    
34.                                         {
    
35.                                                 sum2+=ip[i];
    
36.                                                 i++;
    
37.                                         }
    
38.                                         if(i<size)
    
39.                                         {
    
40.                                                 sum2+=ip[i];
    
41.                                                 if(sum1<=sum2)
    
42.                                                 {
    
43.                                                         end1=i+1;
    
44.                                                         sum1=sum2;
    
45.                                                 }
    
46.                                         }
    
47.                                 }
    
48.                         }
    
49.                         if(sum1>;sum)
    
50.                         {
    
51.                                 start=start1;
    
52.                                 end=end1-1;
    
53.                                 sum=sum1;
    
54.                         }
    
55.                        
    
56.                
    
57.                 }
    
58.                 else
    
59.                 {
    
60.                         i++;
    
61.                 }
    
62.         }
    
63. 
    
64.         cout<<"Start: "<<start<<endl
    
65.                 <<"End: "<<end<<endl;
    
66.         for(i=start;i<=end;i++)
    
67.                 cout<<ip[i]<<" ";
    
68.         cout<<endl
    
69.                 <<"The sum is "<<sum<<endl;
    
70. }
    
71. 
    
72. int main()
    
73. {
    
74.         int a[]={-2,-3,-6,3,4,-1,-2,5,2,-3};
    
75.         MaxSum(a,10);
    
76.         return 0;
    
77. }

复制代码

yuxh

assiss的程序还有问题呀!
int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};

start 0, end 8, sum 14

yuxh

guile的算法也有问题
int a[]={2,3,-4,3,4,3,-2,5,2,-3};

start:3, end:8, sum:15

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. }
    

复制代码

guile

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

start:3, end:8, sum:15

恩，考虑中