迅雷笔试题

yylogo

我记得有一个O(n)的方法

喜猪猪

1. int max_sum(int *array, int array_len)
   
2. {
   
3.     int iTail = 0;
   
4.     int iMaxBit = 0;
   
5.     int iMaxArray = 0;
   
6.     int iSum = 0;
   
7. 
   
8.     if(array_len <= 0 || array == NULL)
   
9.     {
   
10.         return -1;
    
11.     }
    
12.     for(iTail = 0; iTail < array_len; iTail++)
    
13.     {
    
14.         if(iTail == 0)
    
15.         {
    
16.             iMaxBit = array[iTail];
    
17.         }
    
18.         else if(iMaxBit < array[iTail])
    
19.         {
    
20.             iMaxBit = array[iTail];
    
21.         }
    
22. 
    
23.         iSum += array[iTail];
    
24.         if(iSum <= 0)
    
25.         {
    
26.             iSum = 0;
    
27.             continue;
    
28.         }
    
29.         if(iSum > iMaxArray)
    
30.         {
    
31.             iMaxArray = iSum;
    
32.         }
    
33.     }
    
34.     return (iMaxBit <= 0 ? iMaxBit : iMaxArray);
    
35. }

复制代码

davycu

貌似大部分回复都是错的

一生戏

我们前天的一道考试题就是这样的，我们要求用shell实现的，考试时没做出来，考后整出来了
给你参考下思路吧
代码贴在88楼

A.com

望仙乡

万一数组里全是负数呢 ,那个编程珠玑的性能最优的那个算法好像就有问题。

maxsofar=0
maxendinghere =0
for i = [0,n)
maxendinghere =max (maxendinghere+x[i],0)
maxsofar = max(maxsofar,maxendinghere)

是不是得到的结果为0

freesoftsomuch

我们前天的一道考试题就是这样的，我们要求用shell实现的，考试时没做出来，考后整出来了
给你参考下思路吧 ...
一生戏 发表于 2010-09-22 17:17

    感觉你这种算法，全为负是会溢出 max这个底参数调成负,但总有个边界，这个有没有更好的方法,可以把这个边界去掉！在 shell里实现！

一生戏

感觉你这种算法，全为负是会溢出 max这个底参数调成负,但总有个边界，这个有没有更好的方法,可以 ...
freesoftsomuch 发表于 2010-09-23 11:25

今天刚上论坛就看到楼上的消息了
楼上提的问题，后来我也想到了，我用数组的第一个值来作为max的初值

1. #!/bin/bash
   
2. ary=(-9 -12 -120 -8 -20 -100 -30 -89 -20)
   
3. max=${ary[0]}
   
4.         for ((i=0;i<${#ary[*]};i++))
   
5.         do
   
6.                 sum=$(($sum+${ary[i]}))
   
7.                 ary1=(${ary1[*]} ${ary[i]})
   
8.                 if [ $sum -le ${ary[i]} ]
   
9.                 then
   
10.                         ary1=(${ary[i]})
    
11.                         sum=${ary[i]}
    
12.                 fi
    
13. 
    
14.                 if [ $sum -ge $max ]
    
15.                 then
    
16.                         max=$sum
    
17.                         ary2=(${ary1[*]})
    
18.                 fi
    
19.         done
    
20. echo "连续最大的组合为： ("${ary2[*]}")  其和为："$max

复制代码

雨过白鹭洲

这些题目都考烂了。。

greensnow

二楼是对的吧
不过要先遍历一边看看是否全为负数