Re: [問題] 連續整數相乘，求乘積最大?
看板Prob_Solve (計算數學 Problem Solving)作者march20時間16年前 (2008/05/15 18:40)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/6 (看更多)
※ 引述《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
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
