作者tkcn (小安)
看板java
标题Re: [问题] 连续整数,找出乘积最大?
时间Wed May 14 20:33:48 2008
※ 引述《polomoss (小泽)》之铭言:
: 其实已经跟JAVA的语法没有什麽相关~但JAVA版高手众多
: 且不知道去哪问,如果违反版规,或有更适合的地方我自D
: 大概就是
: 使用者给一串整数,要找出它"连续",且乘积最大者
: 例如:
: 5 -2 1 -1 最大 5*-2*1*-1
: -1 2 5 最大 2*5
: 大概是这样
: 不知道有没有高手可以跟我讲想法
: 大概要往哪方面想,或如何着手(不用附上程式码)
: 我只是脑筋有点转不过来~~不过这跟资料结构好像比较有关系
: 不知道要怎麽去跑这个收寻
DP 的解法,
只要填完这张三角形的表格就知道答案了
A1n
.
.
.
A13 A24 ...
A12 A23 A34 ...
X1 X2 X3 X4 ... Xn
------------------------------
其中 X1, X2, ..., Xn 为输入值
Aij 则代表从 Xi~Xj 之乘积,
填此张表格需要 n*(n-1)/2 次乘法。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.239
1F:推 teman:正解! nlgn 05/14 22:30