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

yuxh

楼上说得没错
int m[10] = {-3, -1, -6, -3, -4, -3, -7, -2, -3, -3};
所以
[quote]原帖由 "assiss"]我觉得把负数单独拿出来考虑更好一点[/quote 发表：
也是有道理的

win_hate

因为 yuxh 的精彩算法，此贴评为精彩。

win_hate

我对这个问题作一个简单分析：

一串正负(零)交替的数，把相邻的正数合并求和，把相邻的负数也合并求和，零可分到任何一组当中，得到如下的形式:

1) +A_1, -A_2, +A3, -A4, ......
2) -A_1, +A_2, -A3, +A4, ......

先讨论（1）， A_1 记录为候选最大和。如果 A_1 - A_2 <= 0, 则 ，A_1, -A_2 丢弃，从 A_3 重新计算。否则， A_1 - A_2 + A_3 为候选最大和，依此类推。

再讨论 (2) 如果合并后的序列仍有多项，则 －A_1 可丢弃，从 A_2 开始讨论，这样就归结到了情形（1）。如序列中只有一项（原序列非正），可区别对待，相当于序列求最大值。

实现：
出于对效率的考虑，我们不能把 A_i 一一求出，可用如下方法：

a) 如果开始有负数，现求出这段负数（0）的最大值，并记录。
b) 如果序列未结束，用一个临时变量对后面的一段正数（0)求和，并取代原最大值（最后一次取代）。
c) 如果序列仍未结束，把后一段的负数（0）依次加到该临时变量中。一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。求和的临时变量设为0。如果把该段负数累加完后，临时变量仍不为负，则可再与其后的正数段相加
......


本人的一个实现：

.h

1. 
   
2. struct lms {
   
3.         int l;
   
4.         int r;
   
5.         int sum;
   
6. };
   

复制代码

.c

1. 
   
2. void lms(int *tag, int len, struct lms *info)
   
3. {
   
4.     int sum, tmp, r, l = 0;
   
5. 
   
6. for (r = 0; tag[r] <= 0 && r < len; r++)
   
7.     {
   
8.       l = (tag[l] < tag[r]) ? r : l;
   
9.     }
   
10. 
    
11.   info->l = info->r = l;
    
12.   info->sum = tag[info->l];
    
13.   l = r;
    
14.   sum = 0;
    
15. 
    
16.   while (r < len)
    
17.     {
    
18.       for (; r < len && tag[r] >= 0; r++)
    
19.         sum += tag[r];
    
20. 
    
21.       if (sum > info->sum)
    
22.         {
    
23.           info->sum = sum;
    
24.           info->l = l;
    
25.           info->r = r - 1;
    
26.         }
    
27. 
    
28.       for (; r < len && tag[r] <= 0; r++)
    
29.         {
    
30.           if ((sum += tag[r]) < 0)
    
31.             {
    
32.               for (; r < len && tag[r] <= 0; r++);
    
33.               if (r < len)
    
34.                 {
    
35.                   sum = 0;
    
36.                   l = r;
    
37.                 }
    
38.               r--;
    
39.             }
    
40.         }
    
41.     }
    
42. }
    

复制代码

[ 本帖最后由 win_hate 于 2005-11-22 23:04 编辑 ]

feingnord

如果两个相邻元素是最大的，那和肯定是最大的，这么考虑so simple,
但是相邻这个概念就太模糊，就像二楼恩个一块相邻那种理解也说得过去，
但是超过两个，其中某些元素说自己和其它元素都相邻，揍有点不大对劲。
这种出题方式会把一些逻辑严密思维清晰的人给整死的。嘿嘿

ericooler

看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11:

win_hate

[quote]原帖由 "ericooler"]看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11:[/quote 发表：



我贴出来的是 yuxh 的算法，不是我想出来的。

cattiger

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

复制代码

eagerly1

一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。

这样一来，起点就会失去吧。除非判断时记录

zouyuchong

用线段树做

或者转换成RMQ问题

sasnzy12

比较简单的贪心吧~~（如果贪心不能理解的话 用动态规划好了）
贪心就是把正数与正数合并 负数与负数合并 如果是0就不要
形成一个交错数列 （该数列头尾必须是正数，如果是负数则删除）
然后从头开始 //result是合并以后的交错数列
max=result[0]; (result[0]是正数,result[result.size()-1]也是正数
for (int i=2;i<result.size()-2;i+=2)
  max=(result>;max+result[i-1]+result ? result : max+result[i-1]+result)  //OK

cout<<max<<endl;


贪心 o(N)  （编程相对复杂）
动态规划O(N^2) （10代码行解决问题）
居然还要线段树 ？ %#$%#$%#