最大子数组

难度:简单

描述:

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

样例:

给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为 6

思路分析:

本题只要找出最大和即可,保存两个值,一个为元素之间相加的值(需比较元素相加的值与当前元素的大小),一个为最大值。

代码:

/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
const maxSubArray = function(nums) {
  let max = nums[0]; // 初始化最大值
  let newMax = nums[0]; // 数组元素相加的缓存值
  for (let i = 1; i < nums.length; i++) {
    newMax = Math.max(newMax + nums[i], nums[i]); // 相加是否大于当前值
    max = Math.max(newMax, max); // 与最大值相比
  }
  return max;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

第二种方法更难理解点,可以扩展一下思路:

/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
const maxSubArray = function(nums) {
  var nSum = nums[0]; // 数组元素相加的缓存值
  var nMax = nSum; // 初始化最大值
  for (var i = 1; i < nums.length; i++) {
    var curNum = nums[i]; // 当前元素
    if (curNum >= 0) nSum = nSum > 0 ? nSum + curNum : curNum;
    // 如果两个值都大于0 两个值相加。否则就取后一个大于0的
    else nSum = nSum < curNum ? curNum : nSum + curNum; // 如果新加的值小于0 判断结果是否大于新加的值 小于的话就改为新加的值
    nMax = Math.max(nMax, nSum); // 最大值与数组元素相加值比较
  }
  return nMax;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最大和的数组:

如果你想把最大和的数组都找出来,你需要保存数组的开始下标和结束下标,这里我演示了第一个方法,下面那个方法也是一样:

const maxSubArray = function(nums) {
  let max = {
    num: nums[0],
    start: 0,
    end: 1 // 结束的下标 后面要切割数组 需比当前下标+1.把当前值也切割
  };
  let newMax = {
    num: nums[0],
    start: 0,
    end: 1
  };
  for (let i = 1; i < nums.length; i++) {
    if (newMax.num + nums[i] > nums[i]) {
      // 相加大于当前值 缓存改值和结束下标
      newMax.num = newMax.num + nums[i];
      newMax.end = i + 1;
    } else {
      // 小于当前值 重置start end
      newMax.num = nums[i];
      newMax.start = i;
      newMax.end = i + 1;
    }
    // 最大值被超过 把值赋给最大值
    if (max.num < newMax.num) {
      max.num = newMax.num;
      max.start = newMax.start;
      max.end = newMax.end;
    }
  }
  let arr = nums.slice(max.start, max.end); // 找出最大和的子数组
  return max.num; // 子数组的最大和
};
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

觉得还不错的话,给我的项目点个star

Last Updated: 10/24/2018, 8:07:31 PM