zhxue_11
2018-10-10 12:54
采纳率: 55%
浏览 2.1k

leetcode53,二分法,为什么会超过时间限制?

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));
    }

};

基本上就是抄写的这里的二分法,但是却会超过时间限制,请问为什么呢?

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • cold_windx 2018-10-10 14:02
    已采纳

    最后一个for循环写错了,是++i不是++r

    已采纳该答案
    打赏 评论
  • JonathanYan 2018-10-10 15:08

    楼主可以考虑一下O(N)的算法

    打赏 评论

相关推荐 更多相似问题