Re: [問題] 連續整數，找出乘積最大?
※ 引述《polomoss (小澤)》之銘言：
: 沒想到回覆這麼熱烈~~~
: 其實我也想了整個晚上，連作夢都在想=.=
: 不過看了回覆還是不太懂
好像沒有人看懂我寫的東西 (泣) 直接貼 code 吧 XD
public static int[] findMaxSeq(int[] sequence, int low, int high) {
if (high == low) return new int[] {low, high, sequence[low] };
int pos = 0;
int fneg = high+1, lneg = -1;
int maxleft = 0;
int pleft = 1, pmid = 1, pright = 1;
for (pos=low; pos<=high; pos++) {
if (sequence[pos] == 0) break;
if (sequence[pos] < 0) {
if (fneg > pos) fneg = pos;
if (lneg < pos) {
lneg = pos;
pmid *= pright;
pright = 1;
}
}
if (fneg > high || fneg == pos) pleft *= sequence[pos];
else pright *= sequence[pos];
}
int[] result = new int[3];
if (pos == low) {
result[0] = low; result[1] = low; result[2] = sequence[low];
} else {
// calculate maxleft
if (lneg == fneg) {
pleft /= sequence[lneg];
if (pleft > pright) {
result[0] = low;
result[1] = lneg - 1;
result[2] = pleft;
} else {
result[0] = lneg + 1;
result[1] = pos - 1;
result[2] = pright;
}
} else {
maxleft = pleft * pmid * pright;
if (maxleft >= 0) {
result[0] = low;
result[1] = pos-1;
result[2] = maxleft;
} else {
if (pleft < pright) {
result[0] = low;
result[1] = lneg - 1;
result[2] = pmid * pleft;
} else {
result[0] = fneg + 1;
result[1] = pos -1;
result[2] = pmid * pright;
}
}
}
}
// get right
if (pos < high) {
int[] maxRight = findMaxSeq(sequence, pos+1, high);
if (maxRight[2] > result[2]) result = maxRight;
}
if ((pos == high && result[2] < 0) || result[2] == 0) {
result[0] = low; result[1] = high; result[2] = 0;
}
return result;
}
result[0] <-- max sequence started index
result[1] <-- max sequence ended index
result[2] <-- product of the max sequence
You entered: 0,3,-1,3,2,0,2,-1,3,8,3,-1,-2,5,-3,9,-5,3,0
***************************************************************************
Maximum subset product = 291600
And the sequence is [8 - 17] : 3,8,3,-1,-2,5,-3,9,-5,3
--
很多人以為 所以我要 其實我是個
我是大學生 告訴大家 三十一歲的怪叔叔
● ●/ ︿ ︿
/勁\ <勁 ●
ㄨ /\ ㄨ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225
→
05/15 21:34, , 1F
05/15 21:34, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 11 之 12 篇)：