迅雷笔试题

goubao198562

最大序列肯定是以正数开始 正数结束。如果全是负数就求最大值 先从左边遍历找出第一个正数 同时记录最大值
如果没有正数 那负数最大值就是所求

goubao198562

昨天那个有点问题

goubao198562

void cpu_utility(int *a, int n)
{
        int begin,end,max,sbegin;
        int sum = 0;
        int i = 0;

        max = a[0];
        sbegin = end = 0;
        while (i < n && a[i] < 0)
        {
                if (a[i] > max)
                {
                        max = a[i];
                        sbegin = i;
                        end = i;
                }
                i++;
        }
       
        begin = i;
        if (begin != n)
        {
                for (i = begin;i < n;i++)
                {
                        sum += a[i];
                        if (sum < 0)
                        {
                                sbegin = i+1;
                                sum = 0;
                        }

                        if (sum > max)
                        {
                                max = sum;
                                end = i;
                        }
                }
        }
        begin = sbegin;
        printf("max: %d,begin: %d,end: %d\n",max,begin+1,end+1);
}

petery87

回复 37# shangat

初始化条件改一下，max初始化为数组第一个元素，len初始化为1.
这样以下4种情况都可以处理了。
   0. a[] = { -8, -3, -4, -7, -9, -6, -8, -5, -7}
   1. a[] = { -3, -2, 7, -9, -1}
   2. a[] = { 0, -2, -6, -6, -9, -4, -2, -1, -3}
   3. a[] = { 0, -2, -6, -6, -9, 0, -2, -1, -3}

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.     int a[] = { -8, -3, -4, -7, -9, -6, -8, -5, -7};
   
7.     //int a[] = {0, -1, -2, -3, 0, -4, -8};
   
8.     //int a[] = {1, 1, -3, -3, -4, 3, 4, -8, 2, 3};
   
9.     //int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
   
10.     int start;          /* 子数组开始下标 */
    
11.     int temp_start;     /* 临时计数的数组开始下标 */
    
12.     int len;            /* 子数组长度 */
    
13.     int sum;            /* 临时计数 */
    
14.     int max;            /* 子数组的和 */
    
15. 
    
16.     int i;
    
17.     start = sum = temp_start = 0;
    
18.     len = 1;
    
19.     max = a[0];
    
20. 
    
21.     for(i = 0; i < sizeof(a)/sizeof(a[0]); i ++)
    
22.     {
    
23.         sum += a[i];
    
24.         if(sum < 0)
    
25.         {
    
26.              if(sum > max)      /* 此时的sum即为 a[i],负值的情况只是简单的替换 */
    
27.             {
    
28.                 max = sum;
    
29.                 start = i;
    
30.             }
    
31.             temp_start = i + 1;  /* 从下一个数组元素开始重新计算 */
    
32.             sum = 0;      /* 舍弃前面的元素 */
    
33.         }
    
34. 
    
35.         else if(sum > max)   /* 此时sum不小于0，前面的元素都已舍弃 */
    
36.         {
    
37.             start = temp_start;  /* 找到新的和最大子数组，进行替换 */
    
38.             max = sum;                  /* 替换最大值 */
    
39.             len = i - start + 1;        /* 计算子数组长度 */
    
40.         }
    
41.     }
    
42. 
    
43.     printf("start = %d, len = %d, max = %d\n", start, len, max);
    
44.     return 0;
    
45. }

复制代码

petery87

回复 43# goubao198562


    你的这个begin的计算有问题，比如a[]={0, -3, -2, -4, -1}..  sbegin在sum<0分支会一直后加，这样得到begin就是错的了

chouy

我在别的公司面试也遇到了这道题,当时没答出来,不过后来在家做出来了.
写在了我的BLOG中,地址如下:http://www.cublog.cn/u/10921/showart_2320089.html

笑面狐

DP  啊
王晓东的算法书里面的例子

时间复杂度 O(N)

petery87

回复 46# chouy

如果数组可以回绕的话，只需要对数组遍历两遍就可以了。
粗略的改了一下，可能有些错误。

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.     //int a[] = { -4, -3, -4, -7, -9, -6, -8, -1, -7};
   
7.     //int a[] = {0, -1, -2, -3, 0, -4, -8};
   
8.     //int a[] = {1, 1, -3, -3, -4, 3, 4, -8, 2, 3};
   
9.     //int a[] = {1, -2, 5, -7, -2, 3};
   
10.     //int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
    
11.     int a[] = {9, -12, 120, 8, -20, 100, 30, -19, 20};
    
12.     int start;          /* 子数组开始下标 */
    
13.     int temp_start;     /* */
    
14.     int len;            /* 子数组长度 */
    
15.     int sum;            /* 临时计数 */
    
16.     int max;            /* 子数组的和 */
    
17. 
    
18.     int i = 0;
    
19.     int array_size = sizeof(a)/sizeof(a[0]);
    
20.     start = sum = temp_start = 0;
    
21.     len = 1;
    
22.     max = a[0];
    
23. 
    
24.   //  for(i = 0; i < sizeof(a)/sizeof(a[0]); i ++)
    
25.     while(i < 2*array_size - 1)
    
26.     {
    
27.         sum += a[i % array_size];
    
28. 
    
29.         if(sum < 0)
    
30.         {
    
31.             if(sum > max)
    
32.             {
    
33.                 max = sum;
    
34.                 start = i % array_size;
    
35.             }
    
36.             temp_start = i % array_size + 1;
    
37.             sum = 0;
    
38.         }
    
39.         else if(sum > max && i - temp_start < array_size)
    
40.         {
    
41.             start = temp_start;         /* 发现比之前记录的子数组最大值要大的连续元素，替换开始位置 */
    
42.             max = sum;                  /* 替换最大值 */
    
43.             len = i - start + 1;        /* 计算子数组长度 */
    
44.         }
    
45.         i ++;
    
46.     }
    
47. 
    
48.     printf("start = %d, len = %d, max = %d\n", start, len, max);
    
49.     return 0;
    
50. }
    

复制代码

goubao198562

回复 45# petery87


    对 是有问题

zhrenxi

从第一个依次往后加，  设置两个变量  max 记录曾达到的最大值 ， max start 记录达到最大时的开始下标， m ...
goldenfort 发表于 2010-09-14 14:25

    说得很清楚了