A clean c++ divide and conque approach with O(nlogn) time complexity


  • 1
    Y
    
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
          return findSubArray(nums, 0, nums.size()-1);
            
        }
        
        int findCrossSubArray(vector<int> &nums, int left, int right){
            
            int mid = left + (right-left)/2;
            int leftSum = INT_MIN, rightSum = INT_MIN;
            int sum = 0;
            
            for(int i = mid; i >= left; --i)
            {
                sum += nums[i];
                leftSum = max(leftSum, sum);
            }
            
            sum = 0;
            for(int i = mid+1; i <= right; ++i)
            {
                sum  += nums[i];
                rightSum = max(rightSum, sum);
            }
            
            return leftSum + rightSum;
        }
        
        int findSubArray(vector<int> &nums, int left, int right){
            
            if(left == right)
                return nums[left];
                
            int mid = left + (right-left)/2;
            
            return max(max(findSubArray(nums, left, mid), findSubArray(nums, mid+1, right)), findCrossSubArray(nums, left, right));
        }
    };
    
    

Log in to reply
 

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