redgulli's blog

Max Sum of Rectangle No Larger Than K
By redgulli, history, 6 years ago, In English

I have been trying to solve a LeetCode Problem and I have written a solution for it. I have applied Kadane's algorithm for this problem. But it passes only 21/27 test cases. Could someone please tell how to approach this problem ? I am unable to figure out the approach in the solutions posted online.

This is my code.

int kadane(vector<int>arr, int k){
        int max_sum_so_far=arr[0];
        int max_sum=arr[0];
        for(int i=1;i<arr.size();i++)
        {
            max_sum=max(arr[i],arr[i]+max_sum);
            if((max_sum <=k) && (max_sum >= max_sum_so_far))
                max_sum_so_far=max_sum;
        }
        return max_sum_so_far;
    }
    
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        
        int rows=matrix.size();
        int cols=matrix[0].size();
        int maxsum=numeric_limits<int>::min();
        
        for(int i=0;i<cols;i++){
            int left=i;
            int right=cols;
            vector<int>arr(rows,0);
            while(left < right){
                for(int x=0;x<rows;x++)
                    arr[x]+=matrix[x][left];
                int sum=kadane(arr,k);
                if(sum > maxsum)
                    maxsum=sum;
                left++;
            }
        }
        
        return maxsum;
       
    }
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Few mistakes :

1) You wrote int max_sum_so_far=arr[0];, what if arr[0]>k? Is this a valid initialization for max_sum_so_far? No.

2) Your logic is incorrect. There might be a modification of Kadane which will work but definitely not this one. Use your Kadane function for arr=[-2,-3,11], k=8. Your function gives -2 but it should be 8. Think about why and where your logic is incorrect.

Correct method :

You just need to change the function that you made. Maintain prefix sums in a set and let prefix sum at some index i equals S, then use binary search to find if there exists a prefix sum greater than or equal to S-k, and use it to update your answer. You can use lower_bound for it.

→ Reply