题目：
难度：Easy
相关话题：数组、分治算法、动态规划
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释:连续子数组[4,-1,2,1] 的和最大，为6。
进阶:
如果你已经实现复杂度为 O(n ) 的解法，尝试使用更为精妙的分治法求解。
思路：
O(N)算法就是不断计算前缀和，并且更新最大值，直到sum<0，更新sum=0，继续计算前缀值。 这个算法叫做Kadane算法。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let sum=0,max=nums[0]
for(let i=0;i<nums.length;i++){
sum+=nums[i]
max=Math.max(max,sum)
if(sum<0)sum=0
}
return max
};
O(NlogN)是分治
- 取中间点
mid。 - 计算出左半边
[lo,mid]的最大和以及右半边[mid+1,hi]的最大和。 - 从
mid开始往左和从mid+1开始往右，计算从中间往两边扩展的最大和。
最后取3者最大值。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
return partition(0,nums.length-1)
function partition(lo,hi){
if(lo===hi)return nums[lo]
let mid=Math.floor((lo+hi)/2)
let left=partition(lo,mid),
right=partition(mid+1,hi)
let leftMid=-Infinity,
rightMid=-Infinity
let temp=0
for(let i=mid;i>=lo;i--){
temp+=nums[i]
leftMid=Math.max(leftMid,temp)
}
temp=0
for(let i=mid+1;i<=hi;i++){
temp+=nums[i]
rightMid=Math.max(rightMid,temp)
}
return Math.max(left,right,leftMid+rightMid)
}
};
扩展阅读：