Leetcode刷题100天—53. 最大子序和(分治)—day41

桃扇骨 2022-09-15 11:43 159阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210917173600995][]

#### [53. 最大子序和][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 分治;
    /* * 分治跟归并排序思想差不多 * https://leetcode-cn.com/problems/maximum-subarray/ */
    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<end;i++) { 
        		rightpre+=nums[i];
        		rightmax=Math.max(rightmax, rightpre);
        	}
    // 左右相加获取中间
    // int max=leftmax+rightmax;
    // 递归左,区间是左闭右开[start,pivot)
    // leftmax=maxSubArray(nums,start,pivot);
    // 递归右,区间也是左闭右开[pivot,end)
    // rightmax=maxSubArray(nums,pivot,end);
        	
    // 比较输出
        	return Math.max(leftmax+rightmax,Math.max(maxSubArray(nums,start,pivot),maxSubArray(nums,pivot,end)));
    
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210917173600995]: /images/20220828/e78eabd0aeb74421ac5ce080e7ad5a98.png
[53.]: https://leetcode-cn.com/problems/maximum-subarray/