C++ Divide and Conquer (Algo implementation from Introduction to Algo 3rd)

  • 0

    int maxSubArray(vector<int>& nums) {
    return maxFind(nums, 0, nums.size()-1);
    int maxFind(vector<int>& nums, int low, int high) {

        if (low == high) return nums[low];
        int mid = (low + high)/2;
        //calculate max left, max right
        int maxlow = maxFind(nums, low, mid);
        int maxhigh = maxFind(nums, mid+1, high);
        //calculate middle 
        int i, sum, ml = INT_MIN, mh = INT_MIN;
        for (int i=mid, sum=0; i >= low; i--) {
            sum += nums[i];
            ml = max(sum, ml);
        for (int i=mid+1, sum=0; i <= high; i++) {
            sum += nums[i];
            mh = max(sum, mh);
        return max(ml+mh, max(maxlow, maxhigh));


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.