Can we use divideAndConquer to solve the problem?


  • 0
    Y

    The problem reminds me of the problem "Maximum Subarray "Maximum Subarray, which can be solved by using divideAndConquer. And I try to solve the problem by using divideAndConquer, but I have some troubles with my code.
    What's wrong with my code?

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int size=nums.size();
    		if(size==0) return 0;
    		int res=divideAndConquer(s,nums,0,size-1);
    		return res==INT_MAX?0:res;
        }
    
    	int divideAndConquer(int s, vector<int>& nums,int l,int r)
    	{
    		if(l==r) 
    			if(nums[l]>=s) return 1;
    			else return INT_MAX;
    		int half=(l+r)>>1;
    		int leftMin=divideAndConquer(s,nums,l,half);
    		int rightMin=divideAndConquer(s,nums,half+1,r);
    		int sum=nums[half]+nums[half+1],length=2,left=half-1,right=half+2;
    		while(sum<s)
    		{
    			if(left<l && right>r) {
    				length=INT_MAX;
    				break;
    			}
    			if(left<l)
    			{
    				sum+=nums[right];
    				right++;
    			}else if(right>r)
    			{
    					sum+=nums[left];
    					left--;	
    			}else{
    				if(nums[left]>nums[right])
    				{
    					sum+=nums[left];
    					left--;			
    				}else if(nums[left]<nums[right])
    				{
    					sum+=nums[right];
    					right++;				
    				}else
    				{
    					int previewLeft=left-1,leftSum=0;
    					int previewRight=right+1,rightSum=0;
    					int deta=s-sum;
    					while(leftSum==rightSum )
    					{
    						leftSum+=nums[previewLeft];
    						rightSum+=nums[previewRight];
    						previewLeft--;
    						previewRight++;
    						if(previewLeft<l || previewRight>r || leftSum>=deta || rightSum>=deta) break;
    					}
    					if(leftSum>rightSum && leftSum>=deta){
    						sum+=leftSum;
    						length+=left-previewLeft;
    						break;
    					}else if(rightSum>=deta && leftSum<rightSum)
    					{
    						sum+=rightSum;
    						length+=previewRight-right;
    						break;
    					}
    				}
    			}
    			length++;
    		}
    		return min(length,min(leftMin,rightMin));
    	}
    
    };
    

Log in to reply
 

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