1var arr = [-10, -10, -9, -7, -6, 3, 20, -9, -8, -7];
 2// 找出全部可能的结果对比
 3var max_h = 0,
 4  max_r = 0,
 5  max_s = arr[0];
 6// i从0到n-1
 7for (var i = 0; i < arr.length - 1; i++) {
 8  var sum = 0;
 9  // j从i到n
10  for (var j = i; j < arr.length; j++) {
11    sum += arr[j];
12    // 判断i-j这个区间是否为“最大”
13    if (sum > max_s) {
14      max_h = i;
15      max_r = j;
16      max_s = sum;
17    }
18  }
19}
20console.log(max_h, max_r, max_s);

 1var arr = [-10, -10, -9, -7, -6, 3, 20, -9, -8, -7];
 2
 3// 分治
 4function find_maximum_subarray(arr, low, high) {
 5  if (low == high) {
 6    return { low: low, high: high, max_sum: arr[low] };
 7  } else {
 8    // 递归检查并比较
 9    var mid = Math.floor((low + high) / 2);
10    var left = find_maximum_subarray(arr, low, mid);
11    var right = find_maximum_subarray(arr, mid + 1, high);
12    var cross = find_max_crossing_subarray(arr, low, mid, high);
13    if (left.max_sum > right.max_sum && left.max_sum > cross.max_sum) {
14      return left;
15    } else if (right.max_sum > left.max_sum && right.max_sum > cross.max_sum) {
16      return right;
17    } else {
18      return cross;
19    }
20  }
21}
22
23// 找穿过mid的最大子数组
24function find_max_crossing_subarray(arr, low, mid, high) {
25  var sum = 0,
26    // 注意不是MIN_VALUE，MIN_VALUE 属性是 JavaScript 中可表示的最小的数（接近 0 ，但不是负数）。它的近似值为 5 x 10-324。
27    left_sum = (right_sum = Number.NEGATIVE_INFINITY),
28    max_left,
29    max_right;
30  for (var i = mid; i >= low; i--) {
31    sum += arr[i];
32    if (sum > left_sum) {
33      left_sum = sum;
34      max_left = i;
35    }
36  }
37
38  sum = 0;
39  for (var j = mid + 1; j <= high; j++) {
40    sum += arr[j];
41    if (sum > right_sum) {
42      right_sum = sum;
43      max_right = j;
44    }
45  }
46
47  return {
48    low: max_left,
49    high: max_right,
50    max_sum: left_sum + right_sum,
51  };
52}
53console.log(find_maximum_subarray(arr, 0, arr.length - 1));