当前位置：首页 → 问答吧 → 迅雷笔试题

迅雷笔试题

时间：2010-09-14

来源：互联网

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

作者: davycu 发布时间: 2010-09-14

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

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

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

最后是可以找出来的。

作者: goldenfort 发布时间: 2010-09-14

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

作者: phy0077 发布时间: 2010-09-14

本帖最后由 Mr-Summer 于 2010-09-14 14:49 编辑

有个想法：

for(i=0;i<len;i++)
{
temp[0]=sum;
sum+=array[i];
temp[1]=sum;
result[n]=array[i];
if(temp[0]>temp[1])
{sum=0;if(temp[0]>temp[3]){temp[3]=temp[0];result[]='\0';n=-1;}
n++;
}

复制代码

==================================

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

作者: Mr-Summer 发布时间: 2010-09-14

动态规划

作者: empty141 发布时间: 2010-09-14

暴力法

#include <stdio.h>
int sum(int *array, int array_len)
{
int i;
int sum_data;
sum_data = 0;
for (i = 0; i < array_len; i++) {
sum_data += array[i];
}
return sum_data;
}
int max_sum(int *array, int array_len)
{
int max_data;
int max_start;
int max_end;
int i, j;
int data;
if (array_len > 0) {
max_data = array[0];
max_start = 0;
max_end = 0;
for (i = 0; i < array_len; i++) {
for (j = i; j < array_len; j++) {
data = sum(array + i, j - i + 1);
if (data > max_data) {
max_data = data;
max_start = i;
max_end = j;
}
}
}
printf("{");
for (;max_start <= max_end; max_start++) {
printf("%d", array[max_start]);
if (max_start < max_end) {
printf(", ");
}
}
printf("}\n");
return 0;
}
return -1;
}
#define LENGTH(a) (sizeof(a)/sizeof((a)[0]))
int main(void)
{
int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
max_sum(a, LENGTH(a));
return 0;
}

复制代码

作者: cobras 发布时间: 2010-09-14

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

作者: goldenfort 发布时间: 2010-09-14

回复 davycu

代码如下。

#include <iostream>
using namespace std;
int main()
{
int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
int total;
int maxmum;
int len;
int startindex;
total = maxmum = len = 0;
startindex = 0;
//int i;
for (int i = 0 ; i < sizeof(a)/sizeof(a[0]); i++)
{
total += a[i];
if (total < 0)
{
len = 0;
startindex = i+1;
total = 0;
}
if (total > maxmum)
{
maxmum = total;
len = i - startindex + 1;
}
}
cout << "start index:" << startindex << "\t" << "length:" << len << "\t" << "maxmum:" << maxmum << endl;
return 0;
}

复制代码