本文主要是介绍LeetCode *** 53. Maximum Subarray，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
分析：
这是一个典型的最大子数组问题。可以用分治法来进行解题。
首先先说一些符号：low为数组的最低下标，high为数组最高下标，mid为数组中间的下标。
具体便是，如果数组长度大于1，那么数组的最大子数组一定会出现在[low,mid],[mid,high]或是跨越中点的数组中。
对于[low,mid],[mid,high]的最大子数组又是一个求解最大子数组的问题，那么用递归就可以解决。
而对于跨越中点的数组而言，我们需要对目前的数组来进行一次跨越中点的最大子数组的计算。
这部分的代码为：
int maxCrossingSubArray(vector<int>& nums){int maxLeft=MIN;int sum=0;for(int i=nums.size()/2-1;i>=0;--i){sum+=nums[i];if(sum>maxLeft)maxLeft=sum;}int maxRight=MIN;sum=0;for(int i=nums.size()/2;i<nums.size();++i){sum+=nums[i];if(sum>maxRight)maxRight=sum;}return maxLeft+maxRight;}#define MIN -0xfffffff
class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size()==1)return nums[0];vector<int> left;for(int i=0;i<nums.size()/2;++i){left.push_back(nums[i]);}int maxLeft=maxSubArray(left);vector<int> right;for(int i=nums.size()/2;i<nums.size();++i){right.push_back(nums[i]);}int maxRight=maxSubArray(right);int maxCross=maxCrossingSubArray(nums);if(maxLeft>=maxRight&&maxLeft>=maxCross)return maxLeft;if(maxRight>=maxLeft&&maxRight>=maxCross)return maxRight;return maxCross;}
private:int maxCrossingSubArray(vector<int>& nums){int maxLeft=MIN;int sum=0;for(int i=nums.size()/2-1;i>=0;--i){sum+=nums[i];if(sum>maxLeft)maxLeft=sum;}int maxRight=MIN;sum=0;for(int i=nums.size()/2;i<nums.size();++i){sum+=nums[i];if(sum>maxRight)maxRight=sum;}return maxLeft+maxRight;}
};
这篇关于LeetCode *** 53. Maximum Subarray的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
