LeetCode53 最大子序和
LeetCode53 最大子序和
题目
解题
解题一：动态规划
解题二：分治法
题目
解题
解题一：动态规划
// javascriptvar maxSubArray = function(nums) {
let numLen = nums.length;
let curSum = nums[0], maxSum = nums[0];
for (let i = 1; i < numLen; i++) {
curSum = Math.max(nums[i], curSum + nums[i]);
maxSum = Math.max(maxSum, curSum);
}
return maxSum;};
解题二：分治法
// javascriptvar Status = function(l, r, m, i) {
this.lSum = l;
this.rSum = r;
this.mSum = m;
this.iSum = i;};const pushUp = (l, r) => {
const iSum = l.iSum + r.iSum;
const lSum = Math.max(l.lSum, l.iSum + r.lSum);
const rSum = Math.max(r.rSum, r.iSum + l.rSum);
const mSum = Math.max(l.mSum, r.mSum, l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);};const getInfo = (nums, l, r) => {
if (l === r) return new Status(nums[l], nums[l], nums[l], nums[l]);
const mid = (l + r) >> 1;
const lSub = getInfo(nums, l, mid);
const rSub = getInfo(nums, mid + 1, r);
return pushUp(lSub, rSub);};var maxSubArray = function(nums) {
return getInfo(nums, 0, nums.length - 1).mSum;};
解法二存在的意义：
标签：rSum,const,最大,nums,LeetCode53,iSum,mSum,lSum,子序
来源： https://blog.csdn.net/weixin_45561634/article/details/120669230