By
被删
更新日期:
分治法求最大子数组的javascript实现。
分治法求最大子数组
分治法
分治策略递归求解一个问题，在每层递归中：
- 分解(Divide)步骤：将问题划分未一些子问题，子问题的形式与原问题一样，只是规模更小
- 解决(Conquer)步骤：递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解
- 合并(Combine)步骤：将子问题的解组合成原问题的解
最大子数组问题
求数组的和最大的非空连续子数组，即最大子数组。
分治策略思路
将子数组划分为两个规模尽量相等的子数组，A[low, ..., high]的一个最大子数组A[i, .., j]所处的位置必然是三种情况之一：
- 完全位于子数组
A[low, ..., mid]中，low <= i <= j <= mid
- 完全位于子数组
A[mid + 1, ..., high]中，mid <= i <= j <= high
- 跨越了中点，
low <= i <= mid < j <= high
可递归求解A[low, ..., mid]和A[mid + 1, ..., high]。
求解跨越中点的最大子数组的思路：
- 循环求出
A[i, ..., mid]以及A[mid + 1, ..., j]的最大和
- 合并返回左侧和右侧最大和
js实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| function findMaxSubarray(iArr, low, high) {
function findMaxCrossingSubarray(arr, low, mid, high) {
var leftSum = arr[mid];
var rightSum = arr[mid + 1];
var left = mid,
right = mid + 1;
for (var i = mid, sum = 0; i >= low; i--) {
sum += arr[i];
if (sum > leftSum) {
leftSum = sum;
left = i;
}
}
for (var j = mid + 1, sum = 0; j <= high; j++) {
sum += arr[j];
if (sum > rightSum) {
rightSum = sum;
right = j;
}
}
return [leftSum + rightSum, left, right];
}
if (high === low) {
return [iArr[low], low, high];
} else {
var mid = parseInt((high + low) / 2);
var result1 = findMaxSubarray(iArr, low, mid);
var result2 = findMaxSubarray(iArr, mid + 1, high);
var result3 = findMaxCrossingSubarray(iArr, low, mid, high);
if (result1[0] > result2[0] && result1[0] > result3[0]) {
return result1;
} else if (result1[0] > result2[0]) {
return result3;
} else {
return result3[0] > result2[0] ? result3 : result2;
}
}
}
|
验证
1
2
3
| var inputArr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7];
findMaxSubarray(inputArr, 0, inputArr.length - 1);
|
查看Github有更多内容噢：https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢
如果你想要关注日常生活中的我，欢迎关注“牧羊的猪”公众号噢
