前言：
53. 最大子序和作者：神的孩子在歌唱
大家好，我叫运智
难度简单3710收藏分享切换为英文接收动态反馈
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [0] 输出：0
示例 4：
输入：nums = [-1] 输出：-1
示例 5：
输入：nums = [-100000] 输出：-100000
提示：
- 1 <= nums.length <= 3 * 104
- -105 <= nums[i] <= 105
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
package 分治;
public class _53_最大子序和 {
// 分治:左边遍历，右边遍历，中间遍历
public int maxSubArray(int[] nums) {
// 如果为空或长度为0就返回0
if (nums==null||nums.length==0) {
return 0;
}
return maxSubArray(nums,0,nums.length);
}
// 通过递归思想遍历左右
public int maxSubArray(int[] nums,int start,int end) {
// 如果元素只有1个或0个就结束递归
if (end-start<2) {
return nums[start];
}
// 获取中间节点
int pivot=(start+end)>>1;
// 也许可能在中间的,我们就从中间往左右两边相加，选出最大的子序列
int leftmax=nums[pivot-1];//先获取第一个数
int leftpre=leftmax;
for(int i=pivot-2;i>=start;i--) {//往左边加
// 不断获取数和前面的总值相加，来比较
leftpre+=nums[i];
// 获得序列的最大值
leftmax=Math.max(leftmax, leftpre);
}
// 获取左边
int rightmax=nums[pivot];//获取左边第一个数
int rightpre=rightmax;
for(int i=pivot+1;i
本人csdn博客：https://blog.csdn.net/weixin_46654114
转载说明：跟我说明，务必注明来源，附带本人博客连接。
