本文主要是介绍leetcode 53. Maximum Subarray（分治，递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
找到中间位置，所求子串不是在中间位置的左边，就是右边，还有中间位置两边。中间位置左边右边的和最大的子串可以递归地求得，再求中间位置往左挨个加的最大和以及中间位置往右挨个数的最大和，这两个和就是子串跨越中间位置时的最大和；
这三个最大和中的最大值就是所求最大值。
这道题好像在剑指offer见过额
package leetcode53MaximumSubarray;import java.util.Arrays;public class Solution {public int maxSubArray(int[] nums) {int res=0,i;int len = nums.length;int middle = len/2;if(len == 2){if(nums[0]>=0&&nums[1]>=0)return nums[0]+nums[1];return nums[0]>nums[1]?nums[0]:nums[1];}if(len == 1){return nums[0];}int maxSubLeft,maxSubRight,maxSubMiddle;//System.out.println(0+middle-1);maxSubLeft = maxSubArray(Arrays.copyOfRange(nums, 0, middle));maxSubRight = maxSubArray(Arrays.copyOfRange(nums, middle,len ));int maxMiddleLeft = Integer.MIN_VALUE;int temp = 0;for(i=middle-1;i>=0;i--){temp+=nums[i];if(temp>maxMiddleLeft)maxMiddleLeft=temp;}int maxMiddleRight = Integer.MIN_VALUE;temp = 0;for(i=middle;i<=len-1;i++){temp+=nums[i];if(temp>maxMiddleRight)maxMiddleRight=temp;}int maxMiddle = maxMiddleLeft + maxMiddleRight;if(maxMiddle>=maxSubLeft && maxMiddle>=maxSubRight)res = maxMiddle;if(maxSubLeft>=maxMiddle && maxSubLeft>=maxSubRight)res = maxSubLeft;if(maxSubRight>=maxMiddle && maxSubRight>=maxSubLeft)res = maxSubRight;return res;}public static void main(String args[]){int[] nums = {1,2,-1};//int[] nums = {-2,1,-3};int res = new Solution().maxSubArray(nums);System.out.println(res);}
}
这篇关于leetcode 53. Maximum Subarray（分治，递归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
