Why the Divide-and-Conquer Fails Test Case {1, -1, 1}


  • 0
    W

    The following C++ implementation of Divide-and-Conquer is based on the paper by Bentley in 1984.
    Why Leetcode fails it for the case {1, -1, 1}.
    Expected answer: 1
    This code reports: 2

     class Solution {
        public:
    
        int MaxSubArrayUtil (vector<int>& nums, int start, int end) {                                                                                               
        if (start == end) {
            return nums.at(start);
        }
    
        int middle = (start + end) / 2;
        int left_max = MaxSubArrayUtil(nums, start, middle);
        int right_max = MaxSubArrayUtil(nums, middle + 1, end);
       // int left_suffix_max = nums.at(middle);
        // int right_prefix_max = nums.at(middle + 1);
        int left_suffix_max = 0;
        int right_prefix_max = 0;
        int tmp = 0;
        for (int i = middle; i >= start; i--) {
            tmp += nums.at(i);
            left_suffix_max = max(left_max, tmp);
        }
        tmp = 0;
        for (int i = middle + 1; i <= end; i++) {
            tmp += nums.at(i);
            right_prefix_max = max(right_prefix_max, tmp);
        }
        return max(max(left_max, right_max), left_suffix_max + right_prefix_max);
    }
    
        int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return INT_MIN;
        }
    
        return MaxSubArrayUtil(nums, 0, nums.size() - 1);
        }
    
    };

  • 0
    T
    left_suffix_max = max(left_max, tmp);
    

    is maxing the wrong variables, try

     left_suffix_max = max(left_suffix_max, tmp);

Log in to reply
 

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