※ 引述《sleeper0121 (sleeper)》之铭言：
: 今天去面试，里面有题题目是这样:
: 写个函式，传个整数阵列进去，阵列里面的整数可以是正数、负数或 0
: 请回传一个阵列里面相邻互乘的最大整数值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一个例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 请问这题思考逻辑大概是怎样呢?
: 当下没解出来，害我回家后还一直再想 XD
今天在 facebook 钓出高手，我想应该是最正确的算法了
先从左边乘过去，再从右边乘回来，遇 0 重算，取最大值
以 { 2, -7, 0, 2, 3, 8, -6, 5 } 来说
左边乘过去会得到 2, -14, 0, 2, 6, 48, -288, -1440
右边乘回来会得到 5, -30, -240, -720, -1440, 0, -7, -14
几个值，得到最大值 48
我的实作 http://ideone.com/dmOEEO
没判断子阵列只有一个元素的情况，不过题目也没定义所以就算了 :p

-2, 10, 10, -2 呢？

400 呀

有趣

好妙

赞

(y)

推 再加点判断还可以只要单向算过去就好

这作法还不错 要看单向版本可以看我那篇

推

好方法!

Good

好厉害！！！

引用一楼-2 10 10 -2 -3 呢?(-2 -20 -200 400 -1200) max600忘了还有右边乘回来的

Push

我那篇有右边乘回来同时把last value做动态变动的

楼上 你那篇跑[-2, 2, -2]好像不会算出8?

真的也 那篇只有回原Po的解决方式 看来要加判断式应该还是能在O(n)内解决http://jsfiddle.net/ERKxh/3/ 这是有多一些设定的但是还是不能解决全部算完是正的 晚点来看

0 999 999 999 999 999 999 999 999 999 999 999 999 999 0

要解过大的数字 那只能建质数表 因式分解 最终才用大数

...不是这样吧 ... 这个例子0的位置让他歪打正著

[-0.5, 2, 2, -0.5] 就会算错喔喔喔我搞错如果题目只有整数就是对的

-1,-2,-3,-4,-5,-6,-7

bruceX: 遇到零就重算SansWord, 计算过程中取大的值, 所以反方向算回来就可以holydc: 这...这...这好像是我在你facebook的解法!!!pika0923: 你的是单向没错可是你有考虑过你每次都要做很多次乘积和三数取大/小虽然大家都是O(n), 可是我这边实际跑出数字应该是不会比较慢?!

这个方法改一下就可以单向了乘出负数时若之前没有就记下来若之前有就除掉之前记下的数, 这样就不必反向算回来实际速度会不会比较快就...要测看看 @@更进一步, 只有零的前一个是负数时需要去除, 中间不必这样应该就确定会比较快

刚刚看了一下lovdkkkk, 理论上你的做法应该会快些而且也才是真的one parse(1 parse比2 parse复杂的情况其实就当他不是好了...)

perfact!

现在才看到yp回的 严格说起来用ruby作已经比c慢20倍了XD而最大最小值其实算是为了阅读方便如果玩过这类算法竞赛就会知道 在同一个语言的实作下其实答案对量级对之后实作差异非常小甚至有时候把一堆判断式省掉还会比较快加一堆判断式有时候是省小钱花大钱的作法我还蛮喜欢你这篇的作法就是因为概念简单正确XD

以 C 来说的话, 判断相对于乘/除法是可以忽略的(除非判断的对象本身需要其它运算)真的想再省的话, 只要多记一组数 (3 个 int)就可以把处理和原本判断遇 0 重算的部份写在一起以及在廻圈结束后再处理最后一个数更正, 多记一个 int 应该就够了想成把处理前一个负数包成 function遇零及廻圈结束后再 call 一下就好, 只要多记前一个算的值, 位置则可以直接用推的再更正, 应该也不用多记, 在算下一个之前先处理就好

pika0923: XD 因为我只想得出奇怪的解法XD不过是说 这其实有个复杂的证明在后面...理论上可以用数学归纳法证明...只要证明1~3个数字的数列然后最后在推广他应该就可以lovdkkkk: 我自己实际上去看应该是多记一个负数就可