Kadane’s algorithm for 2D array

Kadane’s algorithm provides an elegant mechanism to find the contiguous subarray within a one-dimensional array of numbers. More regarding this on the Wikipedia page: https://en.wikipedia.org/wiki/Maximum_subarray_problem

This can be extended to 2D array case. I found some implementations:

1. GeeksForGeeks
2. TechQueries

Based on this, I implemented the algorithm in MATLAB.

function [row,col,num_rows,num_cols,sum_max] = max_sub_sum(A)
    summa = -inf;
    [n_rows, n_cols] = size(A);
    
    if n_rows == 1      %% row vector
        [start_index, end_index, mysum] = kadane(A);
        row = 1;
        numrows = 1;
        col = start_index;
        numcols = end_index-start_index+1;
        summa = mysum;
    elseif n_cols == 1  %% col vector
        [start_index, end_index, mysum] = kadane(A');
        col = 1;
        numcols = 1;
        row = start_index;
        numrows = end_index-start_index+1;
        summa = mysum;
    else                %% matrix
        for i=1:n_rows
            tmp = zeros(1,n_cols);
        
            for j=i:n_rows
                tmp = tmp + A(j,:);
                [start_index, end_index, mysum] = kadane(tmp);
            
                if mysum > sum_max
                    col = start_index;
                    num_cols = end_index-start_index+1;
                    row = i;
                    num_rows = j-i+1;
                    sum_max = mysum;
                end
            end
        end
    end
end
    
function [max_start_index, max_end_index, max_sum] = kadane(lin_array)
    max_sum = -inf;
    max_start_index = 0;
    max_end_index = 0;
    
    current_max_sum = 0;
    current_start_index = 1;
    
    for current_end_index = 1:length(lin_array)
        current_max_sum = current_max_sum + lin_array(current_end_index);
        if current_max_sum > max_sum
            max_sum = current_max_sum;
            max_start_index = current_start_index;
            max_end_index = current_end_index;
        end
        
        if current_max_sum < 0
            current_max_sum = 0;
            current_start_index = current_end_index + 1;
        end 
    end
end

The naive implementation of maximum sub-matrix can be achieved by using four for loops.

function [row,col,num_rows,num_cols,sum_max] = max_sub_sum_naive(A)
    [n_rows, n_cols] = size(A);
    sum_max = -inf;
    for beginrow = 1:n_rows
      for begincol = 1:n_cols
          for endrow = beginrow:n_rows
              for endcol = begincol:n_cols
                  submat = A(beginrow:endrow,begincol:endcol);
                  submat_sum = sum(submat(:));
                  
                  if subsum(beginrow, begincol, endrow, endcol) > summa
                      row = beginrow;
                      col = begincol;
                      num_rows = endrow - beginrow + 1;
                      num_cols = endcol - begincol + 1;
                      sum_max = submat_sum;
                  end
              end
         end
    end
end