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;
       
    }