[C++] An clear O(n) divide and conquer solution with comments


  • 31
    W

    For each subarray, calculate four attributes:

    mx (largest sum of this subarray), 
    lmx(largest sum starting from the left most element), 
    rmx(largest sum ending with the right most element), 
    sum(the sum of the total subarray). 
    

    The recurrence is: T(n) = 2T(n / 2) + O(1). So the running time of this algorithm is O(n).

    class Solution {
    public:
        void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
            if (l == r) {
                mx = lmx = rmx = sum = nums[l];
            }
            else {
                int m = (l + r) / 2;
                int mx1, lmx1, rmx1, sum1;
                int mx2, lmx2, rmx2, sum2;
                maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
                maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
                mx = max(max(mx1, mx2), rmx1 + lmx2);
                lmx = max(lmx1, sum1 + lmx2);
                rmx = max(rmx2, sum2 + rmx1);
                sum = sum1 + sum2;
            }
        }
        int maxSubArray(vector<int>& nums) {
            if (nums.size() == 0) {
                return 0;
            }
            int mx, lmx, rmx, sum;
            maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
            return mx;
        }
    };

  • 2
    Z

    thanks , I have been thinking of this method for some time.....


  • 0
    N

    Can someone explain these 4 lines

    mx = max(max(mx1, mx2), rmx1 + lmx2);
        
         lmx = max(lmx1, sum1 + lmx2);
        
          rmx = max(rmx2, sum2 + rmx1);
        
           sum = sum1 + sum2;
    

  • 0
    N
    This post is deleted!

  • 0
    A

    Thanks for sharing, but there are some minor bugs with your codes. For arrays with very large or very small numbers, since you are calculating summation between two int numbers (eg rmx1+lmx2), overflow may occur and leading to wrong results.
    An example might be [INTMIN,INTMIN,INTMIN,INTMIN]


Log in to reply
 

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