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

whpu000625

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

数组m如下：2 3 -6 3 4 3 -2 5 2 -3

则结果为m[3-8]之和15

yuxh

这个题还是有一定难度的

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

复制代码

自己感觉差不多

aero

题是啥意思啊？没明白。

yuxh

就是把相邻的数加起来，取最大值
2 3 -6 3 4 3 -2 5 2 -3 中
3+4+3+(-2)+5+2=15是相邻数相加最大的
下标是从3到8号

liulang0808

用循环嵌套可以的!不过好象比较浪费资源的!

wangxg2

不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。

liulang0808

C的语法已经不太熟悉了,简单描述如下:
MAX=M[0]是最终的最大值;
K为中间作为比较用的;
FOR (I=0;I<=N;I++) 其中N是数组的的大小
{K=M[I];
FOR (J=I;J<=N-1;I++)
{IF (MAX<K) THEN MAX=K;
   K=K+M[J+1];
}
}
已经两年多没有搞编程方面的东西了.
可能存在错误,请指教!

yuxh

考虑下面的这一种普遍情况：
.......m[start]....m[end].....m[start1].....m[end1] m
其中从start到end是结点i之前(称之为“目前”)相邻和最大的序列，和为max
从start1到end1(end1=i-1)是目前相加和>;0的最长序列，和为sum1，如果这样的序列不存在，则sum1=0
用sum表示从start到目前的和

现在新加入了一个结点m，看看最大相邻和序列会发生什么样的变化：
1、sum1 += m; 若sum1 >; max，则从start1到i就变成了最大序列，修正start，end，max；
    sum1 < 0，则表示最近的相邻和>;0的序列不存在了，sum1 = 0;
     否则，修正end1, sum1

2、经过上一步调整后，sum+=m; 如果sum >; max，则从start到i就最成了最大序列，修正end，max
其它的情况保持不变

只需对序列扫描一遍，即可得到相邻和最大序列，O(n)

aero

^_^，全是负数，应该是0吧。因为什么也不加。

yuxh

[quote]原帖由 "wangxg2"]不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。[/quote 发表：

是有这么个问题
所以sum1不应该是最近>;0的最长序列，而应该是最近最大或和>;0的最长序列
改一下：

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

复制代码