免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: davycu

[算法] 迅雷笔试题 [复制链接]

论坛徽章:
0
发表于 2010-09-15 18:36 |显示全部楼层
void cpu_utility(int *a, int n)
{
        int begin,end,max,sbegin;
        int sum = 0;
        int i = 0;

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

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

论坛徽章:
0
发表于 2010-09-15 20:28 |显示全部楼层
不一定哦
按你这算法只能找到9
a1406 发表于 2010-09-15 13:32



    你再想想哦

论坛徽章:
0
发表于 2010-09-15 20:31 |显示全部楼层
回复 8# zhanglistar


8楼的代码在计算startindex(子数组开始位置)和len(子数组长度)时有错误,比如
int a[] = {1, 1, -3, -3, -4, 3, 4, -8, 2, 3};时 会一直进入 (sum<0)分支,startindex被错误的增加了。

对代码做了些修正

  1. #include <stdio.h>

  2. int main()
  3. {
  4.     int a[] = {1, 1, -3, -3, -4, 3, 4, -8, 2, 3};
  5.     /*int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};*/
  6.     int start;          /* 子数组开始下标 */
  7.     int temp_start;     /* */
  8.     int len;            /* 子数组长度 */
  9.     int sum;            /* 临时计数 */
  10.     int max;            /* 子数组的和 */

  11.     int i;
  12.     start = len = sum = max = temp_start = 0;

  13.     for(i = 0; i < sizeof(a)/sizeof(a[0]); i ++)
  14.     {
  15.         sum += a[i];
  16.         if(sum < 0)
  17.         {
  18.             temp_start = i + 1;      /* 从下一个数组元素开始重新计算 */
  19.             sum = 0;
  20.         }
  21.         if(sum > max)
  22.         {
  23.             start = temp_start;         /* 发现比之前记录的子数组最大值要大的连续元素,替换开始位置 */
  24.             max = sum;                  /* 替换最大值 */
  25.             len = i - start + 1;        /* 计算子数组长度 */
  26.         }
  27.     }

  28.     printf("start = %d, len = %d, max = %d\n", start, len, max);
  29.     return 0;
  30. }
复制代码

论坛徽章:
0
发表于 2010-09-15 20:31 |显示全部楼层
你再想想哦
lbaby 发表于 2010-09-15 20:28


churchmice 发表于 2010-09-14 19:22



   这个兄弟的就是这个算法
  1. int max_sum( int array[], int len )
  2. {
  3.   int max_so_far = 0;
  4.   int max = 0;

  5.   for( int i = 0; i < len; i++ ) {
  6.     max_so_far += array[i];
  7.     if( max_so_far > max )
  8.       max = max_so_far;
  9.     if( max_so_far < 0 )
  10.       max_so_far = 0;
  11.   }
  12.   return max;
  13. }

  14. int main( int argc, char *argv[] )
  15. {
  16.   int array[9] = { 9, -12, 120, 8, -20, 100, 30, -89, 20 };
  17.   printf( "%d\n", max_sum( array, 9 ) );
  18.   return 0;
  19. }
复制代码

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2010-09-15 20:47 |显示全部楼层
不合并?   30 -20 30   这样得不合并么?   应该要合并了才是最大连续得集合吧
a1406 发表于 2010-09-15 17:11



    不合并,而是直接用一个Loop来检测这种情况

论坛徽章:
0
发表于 2010-09-15 22:09 |显示全部楼层
迅雷笔试是比较难的。就算一时做不出来也不用纠结。

论坛徽章:
0
发表于 2010-09-15 23:47 |显示全部楼层
33楼 发表于 2010-09-15 20:31


试用 这种数据形式的:
  1. a[] = { -2, -3, -4, -7, -9, -6, -8, -5, -7}
  2. a[] = { 0, -2, -6, -6, -9, -4, -2, -1, -3}
复制代码
负数的情况没考虑到

论坛徽章:
0
发表于 2010-09-16 08:15 |显示全部楼层
我觉得可以先把相邻的正数都相加,化简成正负交叉的数组,O(N)
然后从第一个正数开始判断这个正数值不值得加

论坛徽章:
0
发表于 2010-09-16 08:45 |显示全部楼层
回复 8# zhanglistar


    你这个根本解决不了问题啊。

论坛徽章:
0
发表于 2010-09-16 08:47 |显示全部楼层
回复 33# petery87


    如果数组都是负数的话,岂不歇菜
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP