楼主:
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)