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

brooks_shenzhen

每次从左开始搜索子块，直到子块的部分和blocksum为负时，子块的计算结束；如果当前数组元素为负，子块的部分和为该数组元素值。
if(max < blocksum)
{
        max = blocksum;
        begin = begin1;
        end = i;
}
用来计算最大部分和，并且纪录起始与终止位置

tjsailor

晕，这不就是求最大子序列的问题吗？每本算法书上都有介绍的，不过论坛上有些高手确实说得比书上清楚

爱随柳飘

这里的高手实在是太多了,我都热血沸腾了.
好有冲动,我也要好好学习,天天向上.争取在大家的帮助下,达到一定的境界!!!
努力奋斗!!
加油

爱随柳飘

定义一个max[N]数组,max[0]=0;
然后进行求和比较,先是I=1单个较.将最大值放入max[1]
                           再是I=2,即两个相加的比较,将最大值放到max[2]
                  ...........
                                I=N                                            放到max[N]
最后,就是对数组max比较大小
即为结果了

我等一下写一下去好好写一下程序.

JoeFish

顶楼上的一下，遇到这种问题，我最先想到的还是穷举……虽然笨了点，但是能解决问题

leo_011094

int main(void)
{
  int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};

int maxfar =0 ;
int maxend = 0 ;
int i ;

for(i = 0 ; i  < sizeof(m)/sizeof(int) , i++)
{
  maxend = max(maxend + m[i] , 0);
  maxfar   = max(maxend , maxfar);

}

printf("%d\n" ,maxfar);

exit(0)

}

leo_011094

这个算法应该比较简单。

CUDev

刚看了关于动态规划的一些东西，我也写了一个。

1. 
   
2. #include<cstdio>
   
3. using namespace std;
   
4. 
   
5. //O(n)
   
6. int MaxSum(int n,int *a,int &start,int &end)
   
7. {
   
8.         int sum = 0,b = 0;
   
9.        
   
10.         for(int i = 0;i < n;i++){
    
11.                 if(b > 0){
    
12.                         b += a[i];
    
13.                         end = i;
    
14.                 }
    
15.                 else{
    
16.                         b = a[i];
    
17.                         start = i;
    
18.                 }
    
19. 
    
20.                 if(b > sum)
    
21.                         sum = b;
    
22.         }
    
23. 
    
24.         return sum;
    
25. }
    
26. 
    
27. int main()
    
28. {       
    
29.         int i,j,sum;
    
30.         int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};
    
31.        
    
32.         sum = MaxSum(9,m,i,j);
    
33.         printf("The result is: %d\n",sum);
    
34.         printf("The besti is %d, and the bestj is %d\n",i,j);
    
35.         return 0;
    
36. }
    

复制代码

nopeno

给一个解决的思路，第一遍扫描把连续正的和连续负的都加起来，这样一来得到的数组不是+-+-.... 就是 -+-+.... 形式的，根据例子得到的是 5, -6, 10, -2, 7, -3，然后从正数开始查找开始点和结束点，（如果都是负数，找个最小的负数就是了），如果前面（包括自己）的总和小于后一个负数的绝对值，那么从这个数开始肯定不正确（那么这个点是一个断点），同理找后面的，如刚才的例子， 5是一个断点，另一组的开始点是10，结束点是7，然后剩下的几组比较一下就可以了

masm32

//需要O(n)的空间和O(n)的时间,只能解决最大和>0的情况
//动态规划
//b[j] = max{b[j-1]+a[j],a[j]}.1<=j<=n
//程序如下
int MaxSum(int n,int *a)
{
        int sum = 0;
        int b = 0;

        for(int i=1;i<=n;i++)
        {
                if(b>0)
                        b += a;
                else
                        b = a;
                if(b>sum)
                        sum = b;
        }
        return sum;
}

int main()
{
        int m[10] = {-2,-3,6,-3,4,-3,-2,-1,-2,-3};//MaxSum = 7
        int iRes;

        iRes = MaxSum(10,m);
        printf("%d\n",iRes);                                          //check the answer
        return 0;
}

[ 本帖最后由 masm32 于 2006-8-2 09:00 编辑 ]