请教大家一个算法题目 。

dbcat

题目如下：

   令 X（1）， X（2），X（3）， X（4） 。。。X（n）是一串实数（不需要一定为正数）。
设计一个O（n）的算法，寻找一个（连续的）子序列X（i），X（i+1）。。。X（j），使得它
们的乘积在所有子序列乘积中最大。空子序列的乘积定义为1。

谢谢大家。

win_hate

这个题目跟以前那个最大连续子列和是类似的。

便于讨论，我们先假定 x_1, ..., x_n 中没有负数，则 x_1, ..., x_n 的最大连续子列积对应于 log(x_1), ...,log(x_n) 的最大局部子列和。由于空串有值1，所以最后应把上面求得的串值与1比较。

若 x_1, ..., x_n 中存在负数，则含负数的串不合要求，因为空串值更大。


不过，实现时无需取对数，当前乘积值s为1，x_1 起向后搜索，s = s*x_i, 若 s<1 则从　x_{i+1} 起重新搜索，当前最大值不变；否则，若s大于当前最大值，则更新当前最大值。

win_hate

上面说错了，负数的情况比较复杂，因为含有偶数个负数的串乘积仍是正的。

修改方案为：求绝对值的乘积，并用一个变量记录当前乘积的符号，若负则不更新最大值。即前面的 s=s*x_i 改为 s=s*|x_i|.

[ 本帖最后由 win_hate 于 2006-1-16 19:06 编辑 ]

dbcat

to win_hate
谢谢啊。。。。，我会再想想

foolishfox

空子序列的乘积定义为1。


这个是什么意思?

win_hate

原帖由 woxinfeixiang 于 2006-1-17 16:13 发表



和当前值比较的时候，是每乘以一个数就比较一次吗~~~最好给出一个算式。脑袋笨转不过来！~
等待指教！

先参考这个帖子第6页

http://bbs.chinaunix.net/viewthr ... p;extra=&page=6

看 yzc2002 的代码和我给出的说明。这两个问题是类似的。

win_hate

很遗憾，我上面给出的算法有严重的 bug, 它在序列全为正数时工作得很好，但不能处理负数的情况。

负数该如何处理，我还没想好，期待高手指点。

emacsnw

原帖由 dbcat 于 2006-1-16 00:52 发表
题目如下：

   令 X（1）， X（2），X（3）， X（4） 。。。X（n）是一串实数（不需要一定为正数）。
设计一个O（n）的算法，寻找一个（连续的）子序列X（i），X（i+1）。。。X（j），使得它
们的乘积在所有 ...

1. 
   
2. #include <stdio.h>
   
3.                                                                                 
   
4. double maxprod(double x[],int n)
   
5. {
   
6.     int i;
   
7.     double best = 1,worst = 1,bcurrent = 1,wcurrent = 1,t;
   
8.                                                                                 
   
9.     for(i = 0;i<n;++i){
   
10.         bcurrent *= x[i];
    
11.         wcurrent *= x[i];
    
12.         if(bcurrent>best) best = bcurrent;
    
13.         if(wcurrent>best) best = wcurrent;
    
14.         if(bcurrent<worst) worst = bcurrent;
    
15.         if(wcurrent<worst) worst = wcurrent;
    
16.         if(wcurrent>bcurrent)
    
17.             t = bcurrent,bcurrent = wcurrent,wcurrent = t;
    
18.         if(bcurrent<1) bcurrent = 1;
    
19.         if(wcurrent>1) wcurrent = 1;
    
20.     }
    
21.     return best;
    
22. }
    
23.                                                                                 
    
24. int main()
    
25. {
    
26.     int n,i;
    
27.     double x[100];
    
28.                                                                                 
    
29.     scanf("%d",&n);
    
30.     for(i = 0;i<n;++i) scanf("%lf",&x[i]);
    
31.     printf("%lf\n",maxprod(x,n));
    
32. }
    
33. 
    

复制代码

dbcat

原帖由 emacsnw 于 2006-1-18 04:33 发表


[code]
#include <stdio.h>
                                                                                
double maxprod(double x[],int n)
{
    int i;
    double best = 1,worst =  ...

干的漂亮，太感谢了！