算法_最大子数组

最大子数组

难度：简单

描述：

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

样例：

给出数组[−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;
};

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

/**
 * @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;
};

最大和的数组：

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

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; // 子数组的最大和
};

觉得还不错的话，给我的点个star吧