作者march20 ()
看板Prob_Solve
标题Re: [问题] 连续整数相乘，求乘积最大?
时间Thu May 15 18:40:26 2008
※ 引述《polomoss (小泽)》之铭言：
: 希望大大给点想法，今天写题目的时候卡住了~
: 讲的越详细越好~~
: 使用者给一串整数，要找出它"连续"，且乘积最大者
: 例如:
: 5 -2 1 -1 最大 5*-2*1*-1 = 20
: -1 2 5 最大 2*5 = 10
: 1 2 0 -3 -1 最大 -3*-1 = 3
: 大概是这样~~
: 先谢谢了~
递回式给你, 如果看不懂可能得回去翻翻 dynamic programming 那一章了 :P
令 a(i) 为第 i 个数字, i = 1 ~ n
P(i) 为结束在 a(i) 的连续数列中, 最大正值乘积. 可为零. 如果不存在, 记作 Orz
N(i) 为结束在 a(i) 的连续数列中, 最小负值乘积, 可为零. 如果不存在, 记作 Orz
(注: 0, -3, -4 的" 最小负值" 为 -4)
P(1) = a(1) 如果 a(1) >=0, 否则 P(1) = Orz
N(1) = a(1) 如果 a(1) <=0, 否则 N(1) = Orz
for 1 < i <= n
如果 a(i) > 0
P(i) = Max(a(i), Mult(a(i), P(i-1)))
N(i) = Min(a(i), Mult(a(i), N(i-1)))
如果 a(i) = 0, P(i) = N(i) = 0
如果 a(i) < 0
P(i) = Max(a(i), Mult(a(i), N(i-1)))
N(i) = Min(a(i), Mult(a(i), P(i-1)))
其中 Mult(x, y) = x*y 如果 x,y != Orz, 否则 Mult(x, y) = Orz
Max(x, y) = x 和 y 中, 不是 Orz 的最大非负值. 不存在则 Max(x, y) = Orz
Min(x, y) = x 和 y 中, 不是 Orz 的最小非正值, 不存在则 Min(x, y) = Orz
你要的解就是 P(1) ~ P(n) 和 N(1) ~ N(n) 中, 非 Orz 的最大值
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.136.242.225