序列划分-使其最大值最小化
问题：给指定的序列划分为3份，取每份的最大值，再从3份最大值取出最大的max。如何划分，可以使max最小？
输入：1,2,3,4,5
划分：1,2,3 | 4 |5
最大值为6
思路：两个指针p1,p2，p1索引∈[0,len-2)，p2索引∈[p1+1,len-1),最后一份索引范围[p2+1,len-1]
实现：
输入：1,2,3,4,5
划分：1,2,3 | 4 |5
最大值为6
思路：两个指针p1,p2，p1索引∈[0,len-2)，p2索引∈[p1+1,len-1),最后一份索引范围[p2+1,len-1]
实现：
Array.prototype.sum = function(i,j){
i = i == undefined ? 0 : i;
j = j == undefined ? 0 : j;
var s = 0;
for(var k = i;k <=j ;k++){
s+=this[k];
}
return s;
}
function f(arr){
var result = {val:undefined,p1:"",p2:""};
for(var p1 = 0;p1<arr.length-2;p1++){
var s1 = arr.sum(0,p1);
for(var p2 = p1+1;p2<arr.length-1;p2++){
var s2 = arr.sum(p1+1,p2);
var s3 = arr.sum(p2+1,arr.length-1);
var min = Math.max(Math.max(s1,s2),s3);
if(p1==2){
console.log("min : "+min +",p1:"+p1+",p2:"+p2+",s2:"+s2+",s3:"+s3);
}
if(!result.val || result.val > min){result.val = min;result.p1 = p1;result.p2=p2;}
}
}
return result;
}
console.log(f(new Array(1,2,3,4,5)));