※ 引述《sleeper0121 (sleeper)》之铭言：
: 今天去面试，里面有题题目是这样:
: 写个函式，传个整数阵列进去，阵列里面的整数可以是正数、负数或 0
: 请回传一个阵列里面相邻互乘的最大整数值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一个例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 请问这题思考逻辑大概是怎样呢?
: 当下没解出来，害我回家后还一直再想 XD
闲聊一些 tips
这类型问题算是相当的经 (ㄌㄠˇ) 典 (ㄍㄥˇ)，
(因为有最后附的那个，复杂度更高的经典中的经典...)
就是一个或两个什么列怎样怎样的这种，
经典程度大概是一看就直觉有 O(N) (一列) 或 O(M*N) (二列) 的解，
可能可以一回扫过去这样
临场解题时大致有一定的步骤。
1. 找出逻辑
具体作法就是列几种可能的 case，
多列个几种正负数与零的组合手算一下，
找出 "什么时候要怎样" 这样的规则。
以这题来说大约五个 case 左右就足以找出必要的规则。
2. 写出解法
这有几种选择。
最直接的就是直接照 1 找出的逻辑刻，
或许最基本的暴力解或某种程度的优化。
时间有限下这也是一种选择，
但写字速度可能要够快...
或者可以试着将问题 "视觉化"，
对不同类型的问题有不同的视觉化方法，
例如画圈圈集合图、画棒棒甘特图等，
而以这一题来说，矩阵是很适合的方式。
视觉化有什么好处呢？
就是你只要简单的画好一个有足够代表性的 case，
透过观察其内容便可以很快地找出许多实际运作上的细节，
并且可以不断地在上面比手划脚跑模拟过程。
有没有视觉化的差距大概就像是
1. 写一行字 "秦灭六国"
2. 除了上面这行再给你
这样一张图
这两者的差距
ex 设一数列 1, -1, 2, 3, 0, 1, -2, 2, 3, -5, -4
可以画出像底下的矩阵 (部份省略)
1 -1 2 3 0 1 -2 2 3 -5 -4
1 -1 -2 -6 0
-1
2 6
3
0
1 -2 -4 -12 60 -240
-2
2 120
3
-5
-4
[i, j] 为第 i 位连续乘到第 j 位的值 (这里以把连续算相邻为例)
然后就可以看到在 [1, 5] 遇到 0 时要重算，
重算的动作就是 i = j+1, j = j+2 再继续，
然后就可以耍帅 i = ++j++; 面试官看了不爽 -> 刷掉
然后也很容易看出乘到负的时若前面有出现过负数，
只要除掉前面第一个出现的负数就能取到最大正数，
(这其实就是 以第一个负号切 或 分两群 的部份，
实做上只要除一下就好，不需要真的分子数列)
也能观察出中间的负数不用管，
只要处理阶段的最后一个 (0 的前一个或整个数列的最后一个)。
(因为越乘数字一定越大，
如果之后变正数就不必处理，最后还是负数则只要处理最后的)
从矩阵中经过候选答案的路径也能看出只要一路乘下去就好，
(不过也有此例看不到的,
假设数列为 1, -1, 2, 0, ...，
那在乘到 -2 时若不可取单一数则不能对其做处理，
亦即要判断与最前面出现负数的位置有超过二才能处理)
实际操作上，比起像上例画一个较大的矩阵 (为了举例方便 @@)，
多画几个小 case 可能更有帮助。
视觉化还有几个好处，
首先考官看到你知道要画矩阵辅助应该会加分，
其次写字慢程式难产的话，
靠比手画脚或虚拟码/文字说明搭配矩阵也足以说明。
甚至这也可以是你筛选公司的做法，
假如可以清楚提出好的解只是 code 写不完而被刷掉，
这公司可能不去也罢。(纯举例，不鼓励，请自行负责。)
当然够熟的话就不用视觉化，脑内推推就够了。
附上另一个类似的可以用矩阵表示求解的经典问题，
两个字串找最长共同子序列
longest common subsequence:

推 实用 感谢分享