作者:
TonyQ (自立而後立人。)
2014-07-03 15:03:14※ 引述《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
.........
先以0為切口切成幾個小array,算小array的答案就好小array裡面先算有幾個負數 偶數個直接相乘就是小array的答案,若有奇數個負數,則把第一個或最後一個負數切掉乘乘看就行例如 2,-1,3,-4,5 就試試看2*-1*3跟3*-4*5取大的阿錯了= =2,-1,-3,-4,5就試試看2*-1*-3跟-3*-4*5就行了求得小array的答案後比哪個答案最大就是答案這樣的話應該是O(N)