题目:
给定一个整数数组,找出总和最大的连续数列,并返回总和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1、分治法求解:
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { return subMax(nums, 0, nums.length-1); }; var subMax = function(nums, left, right) { if(left>=right){ return nums[left]; } let mid = left + Math.floor(( right - left ) / 2); let leftMax = subMax(nums, left, mid); let crossMax = crossMid(nums, left, mid, right); let rightMax = subMax(nums, mid + 1, right); return Math.max( leftMax, Math.max(crossMax, rightMax)); }; var crossMid = function(nums, left, mid, right) { let leftSum = -Infinity; let rightSum = -Infinity; let sum = 0; for(let i=mid; i>=left;i--) { sum += nums[i]; if(sum > leftSum) { leftSum = sum; } } sum = 0; for(let i=mid+1; i<=right; i++) { sum += nums[i]; if(sum > rightSum) { rightSum = sum; } } return leftSum + rightSum; };
2、动态规划求解
dp[i]:以nums[i]结尾的连续数列最大和;
转移方程:dp[i]=max(dp[i],dp[i]+dp[i-1]);
一个数是否加入数列取决于前面的数列和是否大于0;
var dp = nums;
dp[i]+=Math.Max(nums[i-1], 0);
将nums数组自身作为dp数组使用;
更新dp[i]的同时寻找最大值max;
var maxSubArray = function(nums) { let len = nums.length; let max = 0; for(let i=1;i<len;++i) { if(nums[i-1]>0){ nums[i]+=nums[i-1]; } if(nums[i]>nums[max]){ max=i; } console.log(nums[i], max); } return nums[max]; };