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

assiss

顶起来。有朋友要。找得好苦。

wxycyel

这也是我的算法：）只不过条件有点不一样，当所有值都小于0时返回0，
稍微改一下既可。
在第2章 算法分析
2.4.3 节中
这是源代码
int MaxSubsequenceSum(const int A[] , int N)
{
    int ThisSum, MaxSum, j;
   
    ThisSum = MaxSum = 0;
    for ( j=0; j<n ; j++)
    {
        ThisSum += A[j];

        if (ThisSum> MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;
    }
    returnh MaxSum;
}

大家如果对算法有兴趣的话不防看看这本书。

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

yzc2002

楼上的看书能不能仔细点?
那本书上给出的算法是

1. int
   
2. 
   
3. max_subsequence_sum( int a[], unsigned int n )
   
4. 
   
5. {
   
6. 
   
7. int this_sum, max_sum, best_i, best_j, i, j;
   
8. 
   
9. 
   
10. 
    
11. /*1*/       i = this_sum = max_sum = 0; best_i = best_j = -1;
    
12. 
    
13. /*2*/       for( j=0; j<n; j++ )
    
14. 
    
15. {
    
16. 
    
17. /*3*/            this_sum += a[j];
    
18. 
    
19. /*4*/            if( this_sum > max_sum )
    
20. 
    
21. {       /* update max_sum, best_i, best_j */
    
22. 
    
23. /*5*/                 max_sum = this_sum;
    
24. 
    
25. /*6*/                 best_i = i;
    
26. 
    
27. /*7*/                 best_j = j;
    
28. 
    
29. }
    
30. 
    
31. else
    
32. 
    
33. /*8*/            if( this_sum < 0 )
    
34. 
    
35. {
    
36. 
    
37. /*9*/                i = j + 1;
    
38. 
    
39. /*10*/               this_sum = 0;
    
40. 
    
41. }
    
42. 
    
43. }
    
44. 
    
45. /*11*/      return( max_sum );
    
46. 
    
47. }
    

复制代码

和之前yuxh的是一样的，而你的程序完全是两码事

win_hate

这个题目说起来有点罗嗦的：

我们尝试从某个 i 开始寻找最大串，
(+ x_i), (+ x_i x_{i+1}) , ...., (+ x_i, ...x_{j-1}) 均非负，但 (+ x_i ... x_j) <0

则 从 x_{j+1} 开始搜索可能的最大串。

此时我们跳过了 x_{i+1}, ..., x{j} ，这是因为

[1] x_{i}... x_{i+l}...x_{j-k}...x_{j}
(+ x_{i+l} ... x_{j-k}) <= (+ x_i ... x_{j-k}) <= 当前 MAX

[2] x_{i}...x_{i+l}....x_{j}....x_{j+k}....
(+ x_{i+l}... x_{j}) <= (+ x_i ... x_{j}) < 0  所以
      (+ x_{i+l}...x_{j+k}) < (+ x_{j+1}....x{j+k})

[1] 说明 x_i ... x_j 之间的串都不如当前找到的大，[2] 说明起始于 x_i, x_j 之间，终结于 x_j 之后的串都不可能是最大串，即使它比当前的 MAX 要大，但从 x_{j+1} 起始的串中有更大的。

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

wxycyel

原帖由 yzc2002 于 2005-11-23 08:58 发表
楼上的看书能不能仔细点?
那本书上给出的算法是
[code]int

max_subsequence_sum( int a[], unsigned int n )

{

int this_sum, max_sum, best_i, best_j, i, j;



/*1*/       i = this_sum = ma ...

如标题

yaomingwei_ren

我的一个比较笨的方法

#include <stdio.h>

int pos1,pos2;
int find(int * array,int size)
{
        int i,j;
        int max=0,sum=0;
        for(i = 0; i<size;i++)
        {
                sum = 0;
                for(j=i;j<size;j++)
                {
                        sum += array[j];
                        if (sum > max)
                        {
                                max = sum;
                                pos1 = i;
                                pos2 = j;
                        }
                }
        }
        return max;
}
int main(int argc, char *argv[])
{
        int array[]={2, 3, -6, 3, 4, 3, -2, 5, 2, -3};
        int max;
        max = find(array,sizeof(array)/sizeof(int));
        printf("max=%d,pos1=%d,pos2=%dn",max,pos1,pos2);
       
        return 0;
}

mingfal

就是O(n)的动态规划吧。

f[n]=max{f[n-1]+a[n],a[n]}

a[n]为第n个元素
f[n]表示以第n个元素为结尾的子串能达到的最大值。

最大的f[n]就是要求的。

emacsnw

O(N^2)的算法就算了吧，前面不久不是有位兄台贴了O(N)的算法了吗？

原帖由 yaomingwei_ren 于 2005-11-23 17:39 发表
我的一个比较笨的方法

#include <stdio.h>

int pos1,pos2;
int find(int * array,int size)
{
        int i,j;
        int max=0,sum=0;
        for(i = 0; i<size;i++)
        {
                sum = 0;
                for(j=i;j<size; ...

大大狗

我也来支持一下，受益匪浅啊

brooks_shenzhen

#include <stdio.h>

#define MAX 9999
void MaxSum(int num[], int length)
{
        int begin, end, begin1;
        int blocksum, max;
        int i;

        max = -MAX;
        i=0;
        while(i < length)
        {
                begin1 = i;
                if(num[i] < 0)
                {
                        blocksum = num[i];
                        if(max < blocksum)
                        {
                                max = blocksum;
                                begin = begin1;
                                end = i;
                        }
                        i++;
                }
                else
                {
                        blocksum = num[i];
                        i++;
                        if(max < blocksum)
                        {
                                max = blocksum;
                                begin = begin1;
                                end = i;
                        }
                        while(blocksum >= 0 && i < length)
                        {
                                blocksum += num[i];
                                if(max < blocksum)
                                {
                                        max = blocksum;
                                        begin = begin1;
                                        end = i;
                                }
                                i++;
                        }
                }
        }

        printf("begin %d, end %d, max %d \n", begin, end, max);
}

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

        MaxSum(num, 10);
}