请教大家一个算法题目 。

dbcat

题目如下：

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

谢谢大家。

tyz

原帖由 emacsnw 于 2006-1-19 14:41 发表


这位兄弟说的对，上次因为有点事情急着走了，贴了代码没来得及仔细解释一下。btw，我这段小程序能够通过上面几位的数据测试。

这个问题其实可以简化成这样：数组中找一个子序列，使得它的乘积最大；同时 ...

哥，你是咋想到的啊

tyz

牛B啊
自惭形秽啊
亏得自己还是科班出身

zhangjinsuo

Code还是有Bug，没有考虑到0的问题
动态规划，应该是MSRA的面试题

zwylinux

我写的一个
#include<stdio.h>
#define SIZE 5
main ()
{
  int max = 0; //记录最大值
  int i;
  int m = 0;//m用来记录出现的第一个非负数的位置
  int k = 0;//k用来记录出现的第一个负数的位置
  int this = 1;//this记录当前积的大小
  int j = 1;//j控制k只记录第一个负数的位置
  int A[SIZE] = {-1,-2,-3,-4,-5 };
  for (i = 0; i < SIZE; i++)
    {
      if (A[i] == 0)//如果遇到0，this重新开始
        {
          j = 1;
          m = i + 1;
          this = 1;
          continue;
        }
      if (A[i] < 0 && j)//j在这里控制k只记录第一个负数的位置
        {
          k = i;
          j = 0;
        }
      this *= A[i];
    max = this > max ? this : max;
    }
  for (i = m; i <= k; i++)
    this /= A[i];
  max = this > max ? this : max;
  printf ("Max=%d\n", max);
}

ArXoR

dp...
记录到当前位置的最大值和最小值就可以了

macrodba

学习ｉｎｇ　　！！！！

dbcat

Excelent！
谢谢各位高手的耐心解答，我又从中学到了不少东西 。
再次向各位致敬

pcboyxhy

很明显
是动态规划

win_hate

我明白了。

设给定的串为 x_1...x_n, emacsnw 的算法对 k 依次求出 x_1...x_k， 中的最大连续乘积。bcurrent 的实质是第 k 步中以 x_k 结尾的串的最大值，而 wcurrent 则是以 x_k 结尾的串中的最小值，其中包括空串。在下面我把 bcurrent 和 wcurrent 简写为 bc(k) 和 wc(k)，看成 k 的函数。

考虑 x_1...x_k 过渡到 x_1...x_{k＋1} 的情形，新增的串均以 x_{k+1} 结尾，我们只需要把新增串的值与 MAX  比较即可。新增串的值不必一一求出，只需求出这些串的最大值，也即 bc(k+1)。而 bc(k+1) 可通过 bc(k) 和 wc(k) 估计出来。设任一新增串为 s.x_{k+1}, 则有

(1) x_{k+1} >= 0
wc(k)<= s <= bc(k) --> wc(k)*x_{k+1} <= s.x_{k+1} <＝bc(k)*x_{k+1} --> wc(k+1)=wc(k)*x_{k+1} 或 1（新增串可为空串）；bc(k+1)=bc(k)*x_{k+1} 或 1。

(2) x_{k+1} <0
wc(k)<= s <= bc(k) --> wc(k)*x_{k+1} >= >=s.x_{k+1} >= bc(k)*x_{k+1} --> wc(k+1)=bc(k)*x_{k+1} 或 1；bc(k+1)=wc(k)*x_{k+1} 或 1。

q.e.d




跟各位讨论大有收益，谢谢！ 尤其是 emacsnw 给出了漂亮的代码。yzc2002 给出的漂亮证明，我在他的证明中理解了 bcurrent 的真正含义。

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