Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { if (!nums.length) { return null; } let start = end = -1; let crtDiff = maxDiff = Number.NEGATIVE_INFINITY; for (let i = 0; i < nums.length; i++) { crtDiff = Math.max(nums[i], crtDiff + nums[i]) maxDiff = Math.max(crtDiff, maxDiff); } return maxDiff; };
To locate the sub array:
var maxSubArray = function(nums) { if (!nums.length) { return null; } let start = end = -1; let crtDiff = maxDiff = Number.NEGATIVE_INFINITY; for (let i = 0; i < nums.length; i++) { crtDiff = Math.max(nums[i], crtDiff + nums[i]) maxDiff = Math.max(crtDiff, maxDiff); if (crtDiff === maxDiff) { if (nums[i] === crtDiff) { start = end = i; } if (maxDiff > nums[i] && start < 0) { start = end = i; } else if (maxDiff > nums[i] && start >= 0) { end = i; } } }
const sub = nums.slice(start, end + 1) return maxDiff; };
// [ 4, -1, 2, 1 ] sum 6
[Algorithm] 53. Maximum Subarray
原文：https://www.cnblogs.com/Answer1215/p/12046404.html