算法_最大子数组&合并排序数组

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

const mergeSortedArray = function(A, B) {
  let newArr = A.concat(B); // 合并数组
  return newArr.sort((a, b) => {
    return a - b; // sort排序
  });
};

const mergeSortedArray = function(A, B) {
  var i, j;
  var arr = [];
  for (i = 0, j = 0; i < A.length && j < B.length; ) {
    // i或者j必须有一个超过对应数组长度 才退出循环 所以至少有一个数组的元素被逐一比较
    if (A[i] < B[j]) {
      // 下面两种写法是一样的
      arr.push(A[i]);
      i++;
    } else {
      arr.push(B[j++]); // 这里会先把j赋值给B[j]， 然后再j++
    }
  }

  // 上面至少有一个数组已经比较了每个元素 如果还有一方长度有剩余 直接push进来就可以(AB一开始就是排序好的数组)
  while (i < A.length) {
    arr.push(A[i++]);
  }
  while (j < B.length) {
    arr.push(B[j++]);
  }
  return arr;
};