c++ divide and conquer solution 8ms


  • 0
    R

    Inspired by Maximun SubArray, divide and conquer algorithm can be utilized here. The difference is finding result cross left subarray and right subarray. We need both consider left subarray suffix min value(lmin) * right subarray prefix min value(rmin) and left subarray suffix max value(lmax)* right subarray prefix max value(rmax)

    '''

    int solver(vector<int> &nums, int start, int end)
    {
        if(start == end)
        {
            return nums[start];
        }
        else
        {
            int mid = (end-start)/2+start;
            int left = solver(nums, start, mid);
            int right = solver(nums, mid+1, end);
            
            int lmin = INT_MAX; int lmax = INT_MIN;
            int rmin = INT_MAX; int rmax = INT_MIN;
            
            long temp = 1;
            for(int i = mid; i>=start; i--)
            {
                temp *= nums[i];
                lmin = lmin < temp ? lmin:temp;
                lmax = lmax > temp ? lmax:temp;
            }
            temp = 1;
            for(int j = mid+1; j<=end; j++)
            {
                temp *= nums[j];
                rmin = rmin < temp ? rmin:temp;
                rmax = rmax > temp ? rmax:temp;
            }
            return max(max(left,right), max(lmin*rmin, lmax*rmax));
        }
        
    }
    

    '''


Log in to reply
 

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