迅雷笔试题

davycu

计算一个整形数组里的连续元素和的最大值
例：{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++一点没考，睡觉去了，大家贴答案，晚上起来看

goldenfort

从第一个依次往后加，  设置两个变量  max 记录曾达到的最大值 ， max start 记录达到最大时的开始下标， max end 记录达到最大时的结束下标，  total 记录当前和。

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

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


最后是可以找出来的。

phy0077

这个是教科书里的经典题目

Mr-Summer

有个想法：

1. 
   
2. for(i=0;i<len;i++)
   
3. {
   
4.     temp[0]=sum;
   
5.     sum+=array[i];
   
6.     temp[1]=sum;
   
7.     result[n]=array[i];
   
8.     if(temp[0]>temp[1])
   
9.         {sum=0;if(temp[0]>temp[3]){temp[3]=temp[0];result[]='\0';n=-1;}
   
10.     n++;
    
11. }
    

复制代码

==================================
理解错了，不过还是觉得应该是缺少一次压栈之类的，不用穷举。

empty141

动态规划

cobras

暴力法

1. 
   
2. #include <stdio.h>
   
3. 
   
4. int sum(int *array, int array_len)
   
5. {
   
6.         int i;
   
7.         int sum_data;
   
8. 
   
9.         sum_data = 0;
   
10.         for (i = 0; i < array_len; i++) {
    
11.                 sum_data += array[i];
    
12.         }
    
13.         return sum_data;
    
14. }
    
15. 
    
16. int max_sum(int *array, int array_len)
    
17. {
    
18.         int max_data;
    
19.         int max_start;
    
20.         int max_end;
    
21.         int i, j;
    
22.         int data;
    
23. 
    
24.         if (array_len > 0) {
    
25.                 max_data = array[0];
    
26.                 max_start = 0;
    
27.                 max_end = 0;
    
28.                 for (i = 0; i < array_len; i++) {
    
29.                         for (j = i; j < array_len; j++) {
    
30.                                 data = sum(array + i, j - i + 1);
    
31.                                 if (data > max_data) {
    
32.                                         max_data = data;
    
33.                                         max_start = i;
    
34.                                         max_end = j;
    
35.                                 }
    
36.                         }
    
37.                 }
    
38.                 printf("{");
    
39.                 for (;max_start <= max_end; max_start++) {
    
40.                         printf("%d", array[max_start]);
    
41.                         if (max_start < max_end) {
    
42.                                 printf(", ");
    
43.                         }
    
44.                 }
    
45.                 printf("}\n");
    
46.                 return 0;
    
47.         }
    
48.         return -1;
    
49. }
    
50. 
    
51. #define LENGTH(a) (sizeof(a)/sizeof((a)[0]))
    
52. 
    
53. int main(void)
    
54. {
    
55.         int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
    
56.         max_sum(a, LENGTH(a));
    
57.         return 0;
    
58. }
    

复制代码

goldenfort

迅雷  还搞嵌入式  ，手伸的长

zhanglistar

回复 1# davycu


    代码如下。

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main()
   
5. {
   
6.     int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
   
7.     int total;
   
8.     int maxmum;
   
9.     int len;
   
10.     int startindex;
    
11.     total = maxmum = len = 0;
    
12.     startindex = 0;
    
13.     //int i;
    
14.     for (int i = 0 ; i < sizeof(a)/sizeof(a[0]); i++)
    
15.     {
    
16.         total += a[i];
    
17.         if (total < 0)
    
18.         {
    
19.             len = 0;
    
20.             startindex = i+1;
    
21.             total = 0;
    
22.         }
    
23. 
    
24.         if (total > maxmum)
    
25.         {
    
26.             maxmum = total;
    
27.             len = i - startindex + 1;
    
28.         }
    
29.     }
    
30. 
    
31.     cout << "start index:" << startindex << "\t" << "length:" << len << "\t" << "maxmum:" << maxmum << endl;
    
32. 
    
33.     return 0;
    
34. }
    

复制代码

blacktt

编程珠玑，第二版

starzhestarzhe

面啥职位啊,迅雷挺好