Share my c++ solution with dp and divide and conquer


  • 0
    P

    DP:

    int maxSubArray(vector<int>& nums) {
    	if (nums.size() == 0) return 0;
    	int thisSum = 0, maxSum = nums[0];
    	for (int i = 0; i < nums.size(); i++)
    	{
    		thisSum += nums[i];
    		maxSum = thisSum > maxSum ? thisSum : maxSum;
    		if (thisSum < 0) thisSum = 0;
    	}
    
    	return maxSum;
    }
    

    Divide and Conquer:

    int maxInThree(int a, int b, int c)
    {
    	int maxNum = a > b ? a : b;
    	maxNum = maxNum > c ? maxNum : c;
    	return maxNum;
    }
    
    int maxSubArraySum(int left, int right, const vector<int>& nums)
    {
    	if (left == right) return  nums[left];
    	int mid = (left + right) / 2;
    	int leftMax, rightMax;
    	int leftBounder = 0, rightBounder = 0;
    	int leftBounderMax = 0, rightBounderMax = 0;
    
    	leftMax = maxSubArraySum(left, mid, nums);
    	rightMax = maxSubArraySum(mid + 1, right, nums);
    	leftBounderMax = nums[mid];
    	for (int i = mid; i >= left; i--)
    	{
    		leftBounder += nums[i];
    		if (leftBounder > leftBounderMax)
    			leftBounderMax = leftBounder;
    	}
    	rightBounderMax = nums[mid+1];
    	for (int i = mid + 1; i <= right; i++)
    	{
    		rightBounder += nums[i];
    		if (rightBounder > rightBounderMax)
    			rightBounderMax = rightBounder;
    	}
    	
    	return maxInThree(leftMax, rightMax, leftBounderMax + rightBounderMax);
    
    
    
    }
    
    
    int maxSubArray2(vector<int>& nums) {
    	if (nums.size() == 0) return 0;
    
    	return maxSubArraySum(0, nums.size()-1, nums);
    	
    }

Log in to reply
 

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