Neat divide and conquer solution


  • 0
    W

    Here is a divide and conquer approach to solve this problem. Tell me if you have a better way to do it.

    int maxSubArray(vector<int>& nums, int l, int u) {
        if (l == u) return nums[l];
        auto m = l + (u - l) / 2;
    
        auto lmax = nums[m];
        for (auto i = m, sum = 0; i >= l; --i) {
            sum += nums[i];
            if (sum > lmax) lmax = sum;
        }
        
        auto rmax = nums[m + 1];
        for (auto i = m + 1, sum = 0; i <= u; ++i) {
            sum += nums[i];
            if (sum > rmax) rmax = sum;
        }
        
        return max({ maxSubArray(nums, l, m), maxSubArray(nums, m + 1, u), lmax + rmax });
    }
    
    int maxSubArray(vector<int>& nums) {
        return maxSubArray(nums, 0, nums.size() - 1);
    }

  • 0
    G

    That's what I was thinking, but that's O(n lg n) (if I'm not mistaken) and O(lg n) space. So much worse than the iterative solution of O(n) time and O(1) space.
    I guess the point of the exercise of divide-conquer is to catch on to the idea of calculating max sub sum from the middle point to the left and to the right.


  • 0
    W

    Yes. I agree with your opinion.


Log in to reply
 

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