※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想 XD
暴力解(in JavaScript)，裡面有應用到部份 DP 的觀念。
var input = [-2,0,3,5,-7];
var result = {sum:input[0],items:[input[0]]};
var stacks = [];
for(var i = 0 ; i < input.length ;++i){
var now = input[i];
if(now == 0){ //優化
stacks.length = 0; //drop old queue
continue;
}
for(var j = 0 ; j < stacks.length ;++ j){
stacks[j].sum *= now;
stacks[j].items.push(now);
if(stacks[j].sum > result.sum){
result.sum = stacks[j].sum;
result.items = stacks[j].items.slice(0);
}
}
stacks.push({sum:now,items:[now]});
if(now > result.sum){
result.sum = now;
result.items = [now];
}
}
console.log(result.sum, result.items);
解題邏輯
[2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
2
2 * -7
-7
0(清queue)
2
2 * 3
3
2 * 3 * 8
3 * 8
8
2 * 3 * 8 * -6
3 * 8 * -6
8 * -6
2 * 3 * 8 * -6 * 5
3 * 8 * -6 * 5
8 * -6 * 5
-6 * 5
5
.........