class Solution {
public:
int maxSubArray(vector<int>& nums) {
return divide(nums, 0, nums.size()-1);
}
private:
int divide(vector<int> &nums,int l,int r){
if(l >= r) return nums[l];
int mid = (l + r) / 2;
int lmax = divide(nums,l,mid - 1);
int rmax = divide(nums,mid + 1,r);
int mid_l = nums[mid];
//计算左边最大的串
for(int i = mid - 1 ,sum = nums[mid];i >= l ;--i){
sum += nums[i];
mid_l = max(sum , mid_l);
}
//与右边的合并
int mid_r = mid_l;
for(int i = mid +1 ,sum = mid_r;i <= r;++r){
sum += nums[i];
mid_r = max(sum,mid_r);
}
return max(lmax,max(rmax,mid_r));
}
};
基本上就是抄写的这里的二分法,但是却会超过时间限制,请问为什么呢?