題目一
給定一個(gè)矩陣matrix统求，其中的值有正、有負(fù)据块、有0码邻，返回子矩陣的最大累加和。
例如另假，矩陣matrix為：
-90 48 78
64 -40 64
-81 -7 66
其中像屋，最大累加和的子矩陣為：
48 78
-40 64
-7 66
所以返回累加和209。
解題思路：
讀題：
code：
function maxArraySum(arr){
if (arr == null || arr.length==0){
return 0;
}
var cur = 0,
max = -1000000;
for(var i = 0;i<arr.length;i++){
cur += arr[i];
max = max>cur?max:cur;
cur = cur>0?cur:0;
}
return max;
}
function maxMatrixSum(arr){
if (arr == null || arr.length == 0 || arr[0].length == 0){
return 0;
}
var cur = 0,
max = -1000000;
var len = arr[0].length;
var newArr = Array.apply(null, Array(len)).map(function(item, i) {
return 0;
});
for (var i = 0;i<arr.length;i++){
for (var j = i;j<arr.length;j++){
for (var k = 0;k<len;k++){
newArr[k] += arr[j][k];
}
max = max>maxArraySum(newArr)?max:maxArraySum(newArr);
}
newArr = Array.apply(null, Array(len)).map(function(item, i) {
return 0;
});
}
return max;
}
maxMatrixSum([[-90,48,78],[64,-40,64],[-81,-7,66]]);
題目二
給定一個(gè)數(shù)組边篮，每個(gè)位置的值代表一個(gè)高度己莺。那么整個(gè)數(shù)組可以看成是一個(gè)直方圖。如果把這個(gè)直方圖當(dāng)作容器的話戈轿，求這個(gè)容器能裝多少水凌受。
例如：
[3,1,2,4]
代表第一個(gè)位置高度為3，第二個(gè)位置高度為1思杯，第三個(gè)位置高度為2胜蛉，第四個(gè)位置高度為4挠进。所以[3,1,2,4]這個(gè)數(shù)組代表的容器可以裝3格的水。
解題思路：
讀題：
code：
function waterProblem (arr){
if (arr == null || arr.length==0){
return 0;
}
var left = 0,
right =arr.length-1,
max = 0,
i = 0,
j = arr.length-1;
while ((i-1) != j){
if (arr[left]<=arr[right]){
if(arr[left]<arr[i]){
left = i;
i++;
}else{
max += arr[left]-arr[i];
i++;
}
}else{
if(arr[right]<arr[j]){
right = j;
j--;
}else{
max += arr[right]-arr[j];
j--;
}
}
}
return max;
}
waterProblem ([3,1,2,4]);
//預(yù)處理數(shù)組解法
題目三
給定一個(gè)數(shù)組誊册，長度大于2领突。找出不相交的兩個(gè)數(shù)組，情況是很多的案怯。請返回這么多情況中君旦，兩個(gè)不相交子數(shù)組最大的和。
例如：
[-1,3,4,-9,1,2]
當(dāng)兩個(gè)不相交子數(shù)組為[3,4]和[1,2]時(shí)可以得到最大的和為10嘲碱。
解題思路：
讀題：不相交的兩個(gè)數(shù)組即從原數(shù)組中間任意位置隔開（不取最后一位）分別取左右數(shù)組的子數(shù)組金砍。即求 i (i>=0&&i<array.length-1)在某個(gè)位置上（左數(shù)組最大連續(xù)累加和）與（右數(shù)組最大連續(xù)累加和）之和最大。//i位置上隔開左數(shù)組包括i位置麦锯，右數(shù)組不包括恕稠。
code：
function twoSubArrayMaxSum(arr){
var cur = 0,
max = -1000000,
maxSum = -100000,
leftArr = [],
rightArr = [];
for (var j = arr.length-1;j>=0;j--){
cur += arr[j];
max = max>cur?max:cur;
cur = cur>0?cur:0;
rightArr[j] = max;
}
max = -1000000;
cur = 0;
for (var i = 0;i<arr.length-1;i++){
cur += arr[i];
max = max>cur?max:cur;
cur = cur>0?cur:0;
maxSum = maxSum>max+rightArr[i+1]?maxSum:max+rightArr[i+1];
}
return maxSum;
}
twoSubArrayMaxSum([-1,3,4,-9,1,2]);
題目四
給定一個(gè)長度為N（N>1）的整形數(shù)組arr，可以劃分成左右兩個(gè)部分离咐，左部分為arr[0..K]谱俭，右部分為arr[K+1..N-1]奉件，K可以取值的范圍是[0宵蛀，N-2]。求這么多劃分方案中县貌，左部分中的最大值減去右部分最大值的絕對值中术陶，最大是多少？
例如：
[2,7,3,1,1]
當(dāng)左部為[2,7,3]煤痕，右部為[1,1]時(shí)梧宫，左部分中的最大值減去右部分最大值的絕對值最大為6。最終返回6摆碉。
解題思路：
讀題：左部分中的最大值減去右部分最大值的絕對值最大塘匣，意味著左部分中的最大值減去右部分最大值的值最大或者右部分中的最大值減去左部分最大值的值最大。即可理解為左右數(shù)組最大值之差最大巷帝。
將數(shù)組劃分成左右兩部分忌卤，原數(shù)組array中最大值MAX必定存在并且可以隨意劃分在左數(shù)組或右數(shù)組中且為所在部分?jǐn)?shù)組最大值。結(jié)果必定為（MAX-左數(shù)組最大值）或者（MAX-右數(shù)組最大值）楞泼，此時(shí)就轉(zhuǎn)為求解存在最小的（左數(shù)組最大值）或最小的（右數(shù)組最大值）驰徊，由于MAX可以隨意劃分到左數(shù)組或右數(shù)組，并且左數(shù)組必定包含左邊界array[0]堕阔，右數(shù)組必定包含右邊界array[array.length-1]即（左數(shù)組最大值）>=array[0]棍厂，（右數(shù)組最大值）>=array[array.length-1] 。所以只要求得min（array[0]超陆，array[array.length-1]）即可得到答案牺弹。結(jié)果為MAX-min（array[0]，array[array.length-1]）。（min求兩者較小值例驹，相等時(shí)隨意染韬）。
code：
function maxABSBetweenLeftAndRight(arr){
var max = -1000000;
for (var i = 0;i < arr.length;i ++){
max = max>arr[i]?max:arr[i];
}
return max = (max-arr[0]>max-arr[arr.length-1])?max-arr[0]:max-arr[arr.length-1];
}
maxABSBetweenLeftAndRight([2,7,3,1,1]);
已上解題思路均來自左神噴火龍講解~~ js代碼原創(chuàng)
