LeetCode-53 最大子序和

本文主要是介绍LeetCode-53 最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

思路想法：

我们可以从头开始遍历，仍然是数组模块的思想，把遍历指向的当前元素和已经形成的子数组分成两个模块A,B（注意：B模块初始为空）；我们只需要考虑：什么时候舍去B模块的这个大尾巴；在加入A模块时，新的B模块是否大于0；大于0就加入，否则不该加入A。并且B模块在此发生断裂，这时我们需要记住B模块存在过的最大值，然后，继续往后遍历。

最后我们得到了很多个 B 模块的最大值，取它们中间的最大的哪个作为答案。

对于上面的示例：按照这个原则；A=-2；B=[]; A+B = -2 不大于 0 ；舍去，但仍保留-2作为第一个B模块的最大值，继续；下一个B模块:B=[]; A = -3; 不大于0；舍去，但仍保留第二个B模块的最大值，继续；下一个 A=4;B=[];A+B=4 大于0；A=-1；A+B=3 大于0；A=2；A+B = 5 大于0；A=1 ;A+B = 6，A=-5；A+B = 1 大于0 A=4；A+B=5 完；在没有断裂的情况下，我们已经在加入新元素的时候，变更了B模块的最大值。

进阶思路：

是的，还有更变态的解法---分治

将原问题分成左右两个子问题，分别求 left 最大子序列 right 最大子序列 和 中间的最大子序列，最后返回 Max(left , mid, right);

Java 代码：

正常解法：

class Solution {public int maxSubArray(int[] nums) {int len=nums.length;// int[] tempMemary = new int[len];   //为每一个旧组保留最大值// tempMemary[0]=nums[0]; // 初始值设定，易错点int[] tempMemary = nums;int tempSum = 0;                   //临时组和int local = 0;for (int i=0;i<len;i++){tempSum += nums[i]; // 首个组的首个临时组和tempMemary[local] = Math.max(tempSum,tempMemary[local]);if (tempSum<=0){ // 表明旧组断裂local++;tempSum = 0;}}int ans = tempMemary[0];for (int k=1;k<len;k++){ans = Math.max(ans,tempMemary[k]);}return ans;}}

分治算法：

class Solution {public int maxSubArray(int[] nums) {if (nums.length== 2){return Math.max(Math.max(nums[0],nums[1]),nums[0]+nums[1]);}if (nums.length==1){return nums[0];}// 以下代码处理nums长度大于2的情况return maxLeftMidRight(nums,0,nums.length-1);}// 递归分治解决问题private int maxLeftMidRight(int[] nums,int left,int right){if (left==right){return nums[left];}if (right-left < 2){return Math.max(Math.max(nums[left],nums[right]),nums[left]+nums[right]);}int mid = left+(right-left)/2; // 下中位数int maxLeft = maxLeftMidRight(nums,left,mid-1);int maxRight = maxLeftMidRight(nums,mid+1,right);int maxMid = maxMidHelper(nums,mid,left,right);return Math.max(Math.max(maxLeft,maxRight),maxMid);}// 此函数帮助找到以中间数为基准找到max子序列private int maxMidHelper(int[] nums,int mid,int left,int right ){int countSum = nums[mid];// mid 向右找int memery_1 = nums[mid];for (int i=mid+1;i<=right;i++){countSum += nums[i];memery_1 = Math.max(countSum,memery_1);}int countSum_1=nums[mid];// 向左找int memery_2 = nums[mid];for (int i=mid-1;i>=left;i--){countSum_1 += nums[i];memery_2 = Math.max(countSum_1,memery_2);}return Math.max(memery_1+memery_2-nums[mid],Math.max(memery_1,memery_2));}}

技能核心：

这里我主要是想谈谈分治：

分治是一种解决问题的思路，它和递归相生相伴。

分治说到底是把大问题分割成较小规模的子问题，这就涉及到了如何分割，我们较为常用的分割是： 下中位数等二分（和二分查找的分法一致，但注意二分查找是针对有序的数组，但是分治是不要求数组有序的），其他条件的分割。

分割完成后，另一个需要考虑的问题就是，如何将分割后的问题组合起来，形成原问题的解，这也是分治法的核心。需要具体问题具体分析。

 

 

 

 

 

 

 

 

 

 

 

这篇关于LeetCode-53 最大子序和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---