53. Maximum Subarray
bytedance,
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.
Solution
hint
粘连型一维 dp[], 需要在子问题多一层转化最优解 为 最大值
子函数 dp[i] 构成为 前i个以nums[i]结尾的数组(例: i=2时, dp[i] 代表以-3 为最终数的所有数组[-2, 1, -3], [1, -3], [-3]的最优解)
关系式为
dp[i] = nums[i] + Math.max(dp[i-1],0)
首项为
dp[0] = nums[0] 限制条件已包含在分解子函数中, 无
然后 在所有解 `dp[]` 中搜索最优解(可与一维dp数组同步循环进行), 搜索结果即为最终解
DP O(n) 原始版
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var res=nums[0], dp=[nums[0]]
for(var i=1;i<nums.length;i++) {
dp[i]=Math.max(dp[i-1]+nums[i], nums[i])
res=Math.max(res, dp[i])
}
return res
};
省空间版
var maxSubArray = function(nums) {
var res=nums[0], prev=nums[0], next
for(var i=1;i<nums.length;i++) {
next=Math.max(prev+nums[i], nums[i])
res=Math.max(res, next)
prev=next
}
return res
}
分治法 O(nlogn) from lucifier
数组nums以中间位置（m)分为左（left)右(right)两部分. 那么有， left = nums[0]...nums[m - 1] 和 right = nums[m + 1]...nums[n-1]
最大子序列和的位置有以下三种情况：
- 考虑中间元素nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。
- 不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
- 不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和
分别求出三种情况下最大子序列和，三者中最大值即为最大子序列和。
var maxSubArray = function(nums) {
return maxSubArr(nums, l, nums.length-1)
}
function maxSubArr(nums, l, r) {
if (l===r) return nums[l]
var mid=(l+r)>>1, suml=0, sumr=0, maxl=-Infinity, maxr=-Infinity
for (var i=mid; i>=l; i--) {
suml+=nums[i]
maxl=Math.max(maxl, suml)
}
for (var i=mid+1; i<=r; i++) {
sumr+=nums[i]
maxr=Math.max(maxr, sumr)
}
var a=maxl + maxr
var b=maxSubArr(nums, l, mid) // KEY: NOT mid-1, or have to deal with l>r
var c=maxSubArr(nums, mid+1, r)
return Math.max(a, b, c)
}