Original link: leetcode-cn.com/problems/ma…

Answer:

  1. Subarrays contain at least one element, meaningnums[i]Must be in a subarray.
  2. nums[i]May be subarrays of elements before or after it. If we iterate backwards, the subarray elements arenums[i]tonums[i + n]That’s going to be iterated overnums[i + n]We can handle it together. So you only need to think about traversalnums[i]And the combination of the previous elements.
  3. Due to thenumsThe numbers are positive and negative, sonums[i]The sum may be negative, so you can discard it. somax[i]There are two cases:
    • Nums [I] is contained in the previous subarray, i.emax[i - 1] + nums[i].
    • Nums [I] is not contained in the previous subarray, i.e0 + nums[i].

    We just need to take the larger between the two, so the state transition equation is:max[i] = Math.max(max[i - 1] + nums[i], 0 + nums[i]);

  4. The sum of the largest suborder obtained at each position is the sum of the largest suborder obtained at each position.
/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function (nums) {
  let max = [nums[0]].// The largest sum of suborders that can be generated by recursively multiplying nums for each value, nums[0] is itself

  // Start from 1
  for (let i = 1; i < nums.length; i++) {
    // The subarray contains at least one element, so you only need to consider nums[I] in the subarray
    // The subarray in which nums[I] is located may contain elements before and after it. Subsequent elements will be computed in subsequent traversals, without judgment
    For nums[I], there are two cases: it can be contained in the previous subarray, or it can regenerate a subarray from itself
    max[i] = Math.max(
      // nums[I] is contained in the previous subarray, and the sum of the previous subsum and nums[I] is the new sum
      max[i - 1] + nums[i],
      // nums[I] is not included in the previous subarray, the last subsum is 0, nums[I] itself is the new subsum
      0 + nums[i]
    );
  }

  // Each position produces a subsequence sum, and the result is the largest one
  return Math.max(... max); };Copy the code
  1. The maximum value can be determined at each pass,maxCan be changed to a variable, store the currently known largest sum of suborders.
  2. The common part of the recursion formulanums[i]I can extract it and save one addition. Since the sum of suborders at each location is related only to the previous location, only one variable is needed to store it.
/ * * *@param {number[]} nums
 * @return {number}* /
var maxSubArray = function (nums) {
  let max = nums[0]; Nums [0] is itself
  let currMax = nums[0]; // Calculate the sum of the suborder of the current position, starting with nums[0]

  // Start from 1
  for (let i = 1; i < nums.length; i++) {
    // Computes the sum of suborders at the current position
    currMax =
      Math.max(
        // nums[I] is contained in the previous subarray
        currMax,
        // nums[I] is not included in the previous subarray. The sum of the previous subarray is 0
        0,) +Nums [I] must be included in the current subarray
      nums[i];
    // Compare the known maximum suborder sum each time
    max = Math.max(max, currMax);
  }

  // The maximum suborder sum is already generated in the loop
  return max;
};
Copy the code