迅雷笔试题

lbaby

假设序列：
A1 ... Ai
中已找出了最大的连续，现在考虑下一个元素： Ai+1

那么，现在的最大连续序列，要么在A1... Ai中，要么包含 Ai +1 。

初始情况：
若序列中无元素则最长序列和为0

a1406

假设序列：
A1 ... Ai
中已找出了最大的连续，现在考虑下一个元素： Ai+1

那么，现在的最大连续序列， ...
lbaby 发表于 2010-09-15 12:52

不一定哦
按你这算法只能找到9

a1406

把连续得正数和负数合并
再把负数两边得正数都大于该负数得数合并
最后最大得那个正数得集合就是结果

robin254817

回复 1# davycu


    感觉俩for循环就行了：（代码没测试，感觉应该可以）
   int max_sum(int *array,int array_len){
      int max_tmp = 0,max = 0;
      int i,j;

      for(i  = 0;i < array_len;i++){
           for(j = i;j < array_len;j++){
                  max_tmp += array[j];
                  if(max_tmp > max)
                     max = max_tmp;
           }
      }
     return max;
   }
刚刚公司搬家换了台机器，没装LINUX，没编译运行,不知道结果。

robin254817

回复 24# robin254817


    忽略了一点。int max = -2147483648,可能max最后结果为负值。

   int max_sum(int *array,int array_len){
      int max_tmp = 0,max = -2147483648;
      int i,j;

      for(i  = 0;i < array_len;i++){
           for(j = i;j < array_len;j++){
                  max_tmp += array[j];
                  if(max_tmp > max)
                     max = max_tmp;
           }
      }
     return max;
   }

robin254817

回复 12# churchmice


    如果数组里全部都是负值怎么办？

liexusong

我也想问下：什么是连续元素

folklore

把连续得正数和负数合并
再把负数两边得正数都大于该负数得数合并
最后最大得那个正数得集合就是结果
a1406 发表于 2010-09-15 13:36

正解，但第二步不能合并了(合并是破坏性的），第二步是用一个Loop遍历

shangat

根据 #24 楼提议，俩 for ：

1. #include<stdio.h>
   
2. #define N 10
   
3. // 只要结果
   
4. int a[N];
   
5. 
   
6. int max_sum ( int *array, int array_length ) {
   
7.     int tags = 0;
   
8.     int max, i, j, k, m;
   
9.     for (i = 0; i < array_length; i++ ) {
   
10.         max = 0;
    
11.         for ( j = i; j < array_length; j++ ) {
    
12.             max += array[j];
    
13.             if ( tags < max || tags == 0 ) {
    
14.                 k = i;
    
15.                 m = j;
    
16.                 tags = max;
    
17.             }
    
18.         }
    
19.     }
    
20.     printf ("the max sum is %3d ,from %3d to %3d\n",tags,k+1,m+1 );
    
21. }
    
22. 
    
23. main () {
    
24.     int i;
    
25.     int *p;
    
26.     for (p = a; p < a+ N; p++ )
    
27.         scanf ("%d",p);
    
28.     p = a;
    
29.     max_sum ( p, N );
    
30. }

复制代码

1. #include<stdio.h>
   
2. #define N 10
   
3. // 显示每次的结果,再作选择
   
4. int a[N];
   
5. 
   
6. int max_sum ( int *array, int array_length ) {
   
7.     int max ;
   
8.     int tags, i, j, k, m;
   
9.     for (i = 0; i < array_length; i++ ) {
   
10.         max = tags = 0;      
    
11.         for ( j = i; j < array_length; j++ ) {
    
12.             max += array[j];
    
13.             if ( tags < max || tags == 0) {
    
14.                 k = i;
    
15.                 m = j;
    
16.                 tags = max;
    
17.             }
    
18.         }
    
19.         printf ("In %3dth  the max sum is %3d ,from %3d  to %3d\n",i+1,tags,k+1,m+1 );
    
20.     }
    
21. }
    
22. 
    
23. main () {
    
24.     int i;
    
25.     int *p;
    
26.     for (p = a; p < a+ N; p++ )
    
27.         scanf ("%d",p);
    
28.     p = a;
    
29.     max_sum ( p, N );
    
30. }

复制代码

a1406

正解，但第二步不能合并了(合并是破坏性的），第二步是用一个Loop遍历
folklore 发表于 2010-09-15 17:02

不合并？   30 -20 30   这样得不合并么？   应该要合并了才是最大连续得集合吧