免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 50187 | 回复: 104

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

论坛徽章:
0
发表于 2010-09-14 14:10 |显示全部楼层
计算一个整形数组里的连续元素和的最大值
例:{9, -12, 120, 8, -20, 100, 30, -89, 20}
结果是{120, 8 , -20, 100, 30}的和最大,为 238
函数声明:
int max_sum(int *array, int array_len);
不会做,想把所有可能的和都给算出来再查找,没好意思写...

迅雷嵌入式开发的,昨晚通宵背C++语法,结果C++一点没考,睡觉去了,大家贴答案,晚上起来看

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2010-09-14 14:25 |显示全部楼层
从第一个依次往后加,  设置两个变量  max 记录曾达到的最大值 , max start 记录达到最大时的开始下标, max end 记录达到最大时的结束下标,  total 记录当前和。

开始时  max=0 max start=0  max end=0  total=0;

只要 什么时候  total <=0 , 就断开, 重新计算。


最后是可以找出来的。

论坛徽章:
1
午马
日期:2013-08-23 23:39:47
发表于 2010-09-14 14:38 |显示全部楼层
这个是教科书里的经典题目

论坛徽章:
1
申猴
日期:2014-04-18 16:29:14
发表于 2010-09-14 14:41 |显示全部楼层
本帖最后由 Mr-Summer 于 2010-09-14 14:49 编辑

有个想法:

  1. for(i=0;i<len;i++)
  2. {
  3.     temp[0]=sum;
  4.     sum+=array[i];
  5.     temp[1]=sum;
  6.     result[n]=array[i];
  7.     if(temp[0]>temp[1])
  8.         {sum=0;if(temp[0]>temp[3]){temp[3]=temp[0];result[]='\0';n=-1;}
  9.     n++;
  10. }
复制代码
==================================
理解错了,不过还是觉得应该是缺少一次压栈之类的,不用穷举。

论坛徽章:
0
发表于 2010-09-14 14:43 |显示全部楼层
动态规划

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2010-09-14 14:45 |显示全部楼层
暴力法

  1. #include <stdio.h>

  2. int sum(int *array, int array_len)
  3. {
  4.         int i;
  5.         int sum_data;

  6.         sum_data = 0;
  7.         for (i = 0; i < array_len; i++) {
  8.                 sum_data += array[i];
  9.         }
  10.         return sum_data;
  11. }

  12. int max_sum(int *array, int array_len)
  13. {
  14.         int max_data;
  15.         int max_start;
  16.         int max_end;
  17.         int i, j;
  18.         int data;

  19.         if (array_len > 0) {
  20.                 max_data = array[0];
  21.                 max_start = 0;
  22.                 max_end = 0;
  23.                 for (i = 0; i < array_len; i++) {
  24.                         for (j = i; j < array_len; j++) {
  25.                                 data = sum(array + i, j - i + 1);
  26.                                 if (data > max_data) {
  27.                                         max_data = data;
  28.                                         max_start = i;
  29.                                         max_end = j;
  30.                                 }
  31.                         }
  32.                 }
  33.                 printf("{");
  34.                 for (;max_start <= max_end; max_start++) {
  35.                         printf("%d", array[max_start]);
  36.                         if (max_start < max_end) {
  37.                                 printf(", ");
  38.                         }
  39.                 }
  40.                 printf("}\n");
  41.                 return 0;
  42.         }
  43.         return -1;
  44. }

  45. #define LENGTH(a) (sizeof(a)/sizeof((a)[0]))

  46. int main(void)
  47. {
  48.         int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
  49.         max_sum(a, LENGTH(a));
  50.         return 0;
  51. }
复制代码

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2010-09-14 14:56 |显示全部楼层
迅雷  还搞嵌入式  ,手伸的长

论坛徽章:
0
发表于 2010-09-14 15:18 |显示全部楼层
回复 1# davycu


    代码如下。
  1. #include <iostream>
  2. using namespace std;

  3. int main()
  4. {
  5.     int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
  6.     int total;
  7.     int maxmum;
  8.     int len;
  9.     int startindex;
  10.     total = maxmum = len = 0;
  11.     startindex = 0;
  12.     //int i;
  13.     for (int i = 0 ; i < sizeof(a)/sizeof(a[0]); i++)
  14.     {
  15.         total += a[i];
  16.         if (total < 0)
  17.         {
  18.             len = 0;
  19.             startindex = i+1;
  20.             total = 0;
  21.         }

  22.         if (total > maxmum)
  23.         {
  24.             maxmum = total;
  25.             len = i - startindex + 1;
  26.         }
  27.     }

  28.     cout << "start index:" << startindex << "\t" << "length:" << len << "\t" << "maxmum:" << maxmum << endl;

  29.     return 0;
  30. }
复制代码

论坛徽章:
0
发表于 2010-09-14 15:43 |显示全部楼层
编程珠玑,第二版

论坛徽章:
0
发表于 2010-09-14 15:46 |显示全部楼层
面啥职位啊,迅雷挺好
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

ITPUB技术栈

ITPUB技术栈是ITPUB企业打造的垂直于IT领域的知识社群平台,在这里,你既可以是创作者也可以是消费者。如果你的IT生涯丰富多彩,喷薄的个人价值尽可在小栈内体现;如果你渴望找到志同道合的伙伴,拓宽人脉,小栈比跑会场更快。 小栈特色:
1.极高的用户转化率,实现更直接的知识变现;
2.随时随地,刷个朋友圈的时间,实现更长效的信息沉淀;
3.戳痛、难点的专业咨询,更接近成功解决方案的时刻;
4.贴近意见领袖,个人高速成长,迈入更富有价值的人际圈。

----------------------------------------

技术小栈>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP