作者cai7773 (0.0)
看板java
标题Re: [问题] 连续整数，找出乘积最大?
时间Wed May 14 19:39:16 2008
※ 引述《polomoss (小泽)》之铭言：
: 其实已经跟JAVA的语法没有什麽相关~但JAVA版高手众多
: 且不知道去哪问，如果违反版规，或有更适合的地方我自D
: 大概就是
: 使用者给一串整数，要找出它"连续"，且乘积最大者
: 例如:
: 5 -2 1 -1 最大 5*-2*1*-1
: -1 2 5 最大 2*5
: 大概是这样
: 不知道有没有高手可以跟我讲想法
: 大概要往哪方面想，或如何着手(不用附上程式码)
: 我只是脑筋有点转不过来~~不过这跟资料结构好像比较有关系
: 不知道要怎麽去跑这个收寻
恩 我的想法是 :
把输入的数 分成5群 : A : {X|X<=-1} = { a1, a2, ... , an } , |A|=N
where a1 <= ... <= an
B : {X|-1<X<1}
C : {X|X>=1} = { c1, c2, ... ,cn} , |C| = M
然後 答案就是 : if ( N 是奇数 ){
N-1 M
ans = Π Ai * Π Ci ; }
i=1 i=1
else {
N M
ans = Π Ai * Π Ci; }
i=1 i=1
m
* Π Ai = An * A(n+1) * A(n+2) * ... * Am
i=n
恩恩 应该这是你要的答案的算法~~ 其中会有把资料做排序的( sorting )~~
跟做分群的(这应该用一堆 if-else 和 array 可以处理) 方法
以上是我的想法 虽然没有提供啥资料结构或是扣的 (汗)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.116.103.140
※ 编辑: cai7773 来自: 140.116.103.140 (05/14 19:42)
1F：推 superlubu:原 PO 的问题是要"连续"，也就是说要维持原本的次序 05/14 21:00
2F：→ cai7773:嘿嘿拍谢 = = 我以为是不用连续 囧rz 05/14 21:13
3F：推 polomoss:这样没有连续耶~~不过还是感谢大大分享 05/14 23:03