迅雷笔试题

freesoftsomuch

今天刚上论坛就看到楼上的消息了
楼上提的问题，后来我也想到了，我用数组的第一个值来作为max的初值
一生戏 发表于 2010-09-24 20:52

    这个代码没问题了，不过${#array(*)},${#array(@)}这两个有区别没有，如果有那么区别是什么。谢谢{:3_198:}

xishuaiya

1. int max_sum(int *array, int len)
   
2. {
   
3.         int maxval = maxs(array, len);
   
4.         int tmp = 0;
   
5.         for(int i = 1;i < len;i++)
   
6.         {
   
7.                 tmp = maxs(array + i, len - i);
   
8.                 if(tmp > maxval) maxval = tmp;
   
9.         }
   
10. 
    
11.         return maxval;
    
12. }
    
13. 
    
14. //计算以array开始的i（i=1,2...len）个连续元素的和，然后返回最大值
    
15. int maxs(int *array, int len)
    
16. {
    
17.         int maxval(0),tmp(0);
    
18.         for(int i = 0;i < len;i++)
    
19.         {
    
20.                 tmp        += array[i];
    
21.                 if(tmp > maxval) maxval = tmp;
    
22.         }
    
23. 
    
24.         return maxval;
    
25. }

复制代码

wsysx

昨天去金山笔试 也考这道题了

moosewoler

看了10几页，就a1406和我思路一样的啊。
大家全是直接贴代码？有没有讨论规律的。。。。

全负神马的都小case了。
不知道大家有没有考虑多解的情况？

yffbrave

Absolute Dynamic Programming !!

rick_cheung

回复 91# freesoftsomuch


    《编程之美》上有原题

septem776

DP,随便写了下，时间复杂度O(n)：

int max_sum(int *array, int array_len)
{
    int maxn, f[100];
    maxn = array[0];
    f[0] = array[0];
    for(int i=1; i<array_len; i++)
    {
        f[i] = max(f[i-1]+array[i], array[i]);
        if(maxn < f[i])
            maxn = f[i];
    }
    return maxn;
}

DNFCF

haioulove

1.先找第一个正整数，如果没找到，说明全是负数。
2.如果找到了，那就一直加，直到遇到一个正整数。
3.如果遇到了，那就看现在的和是否大于零，大于零的话，重复做下去，小于零的话，丢弃掉，
从后面的第一个大于零的书在开始。
4。如果没遇到（到达末尾了），那就从当前序列中剔掉后面的负数。
其他的边界条件你就自己去想吧！

cddesire

经典问题，最大字段和问题，用动态规划O（n），用分治O(nlogn)