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

assiss

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

guile

佩服yuxh的算法，觉得我考虑问题真是含糊不清。
后来把程序又写了一下，先贴了再研究yuxh的程序

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

复制代码

whpu000625

呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的

aero

yuxh提出的算法不就是O（n）的吗？

lisp

[quote]原帖由 "whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法[/quote 发表：

呵呵，表示怀疑

guile

[quote]原帖由 "whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的[/quote 发表：


真的吗？那我心情好受一些，当时我可是本来想自己做出来，想了一下午还是不对，看了yuxh的算法才算弄懂。
总之打击很大，第二天花100多块钱买了两本算法书...这样说的话我便舒心多了，不过更佩服yuxh了

assiss

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

guile

[quote]原帖由 "assiss"]怎么可能啊。骗小孩的，guile也相信？[/quote 发表：


唔，还是等眼见为实。如果whpu000625能给出出处我便信了。

cattiger

阅读了yuxh的算法，改造了一下，使逻辑统一一下：
各位验证一下

1. #include <stdio.h>;
   
2. void MaxSum(int *ary, int n)
   
3. {
   
4.     int i, start=0, end=0, start1=0, max, sum;
   
5. 
   
6.     max=sum=ary[0];
   
7.    
   
8.     for(i=1; i<n; i++)
   
9.    {
   
10.         if(ary[i] >; 0 && sum <= 0)
    
11.        {
    
12.             start1 = i;
    
13.         }
    
14.                
    
15.         sum += ary[i];
    
16.                
    
17.        if(sum<0)
    
18.       {
    
19.             start1=i;
    
20.       }
    
21. 
    
22.         if (sum >; max)
    
23.       {
    
24.              start = start1;
    
25.              end = i;
    
26.              max = sum;
    
27.        }
    
28.         else if(sum < 0)
    
29.       {
    
30.             sum = 0;
    
31.       }
    
32.     }
    
33.     printf("start %d, end %d, sum %d\n", start, end, max);
    
34. }
    
35. void main()
    
36. {
    
37.     int m[10] = {2, 3, -6, 3, 4, 3, -7, 5, 3, -3};
    
38. 
    
39.     MaxSum(m, 10);
    
40.        
    
41.     return;
    
42. }

复制代码

eagerly1

原帖由 "cattiger" 发表：

1. if(ary[i] >; 0 && sum <= 0)
   
2.        {
   
3.             start1 = i;
   
4.         }
   
5.       
   
6.         sum += ary[i];
   

复制代码

似乎应该为：

1. if(ary[i] >; 0 && sum <= 0)
   
2.        {
   
3.             start1 = i;
   
4.             sum=0;
   
5.         }
   
6.       
   
7.         sum += ary[i];
   

复制代码