※ 引述《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