Find submatrix with the maximum sum

This is homework, but I am really stuck and would be very greatful if someone could help me on the way! The aim of the exercise is to find the submatrix of matrix A that has the highest sum. The function should return the row and column indices of where the submatrix starts, the dimensions of the submatrix and the sum of the submatrix. So far this is my code

function [row,col,numrows,numcols,summa] = maxsubsum(A)
[row, col] = size(A);
for r = 1:row
    for c = 1:col
        B = A(r:end, c:end);
        C = sum(B);
        % need something here that stores the highest sum %
    end
end
for r = 1:row
    for c = 1:col
        D = A(end:r, end:c);
        E = sum(D);
        % need something here that stores the highest sum and indices %
    end
end

The thought is that in order to find all submatrices I need to start in both upper-left corner and lower-right corner. However, I am not sure about how I can find and store the highest sum. Can anyone give me a hint on the way?

Answer 1

[Image Analyst]

Charlotte: Your code won't do it. The problem is that your submatrices all have the lower right corner as part of them. Obviously, this will give you only a very small subset of all possible submatrices. The way to do it is actually very simple. There is already a function to take the sum of all submatrices of a fixed size, and that function is called conv2(). So all you need to do is to call conv2 for all possible window sizes. Keep track of the max and location. Since the location will be half a window width inside, you need to add half the window width. So if m is your full size matrix, you just need to do

[rows, columns] = size(m)
for width = 1 : columns
    for height = 1 : rows
        kernel = ones(rows, columns); % Sum up within this window shape.
        out = conv2(m, kernel, 'valid');
        if max(out(:)) > maxSoFar
           % Get and save location
        end
    end
end
% Now add floor(rows/2) to the y location of the max, and floor(columns/2) to the x location of the max.

I've left out some for you to do, since it's your homework. See Adam's answer for how to save the result for a certain window shape/size, if you need to (because it's more than the old max).

So, do you see how the double for loop gives all possible submatrix sizes? And do you see how conv2() will get the sum for the given submatrix size for all locations in the matrix (so no need for yet another double nested for loop)?

It's perhaps a bit of a clever trick but I think once you, or anyone, understands what it's doing, you'll realize that it will do the job you need (whereas your code won't).

Answer 2

[Thorsten]

You can set maxval = -Inf; before the loop and then compare if the sum of the current submatrix is greater than maxval: if so, set maxval to this value and also store the row, column, and dimension of your submatrix.

Answer 3

[Adam]

Without wanting to do your homework for you, this is a general framework that is often used for keeping track of a maximum and its location when searching through an (in this case 2d) array of data

 maxSoFar = -Inf;
 iForMax = [];
 jForMax = [];

for i = 1:10
   for j = 1:10
      maxVal = someCalculation( );

        if maxVal > maxSoFar
           maxSoFar = maxVal;
           iForMax = i;
           jForMax = j;
        end
     end
  end

You should be able to do something similar

[charlotte88]

Thank you so much Adam! Hopefully, I will manage to do it now!

Answer 4

[charlotte88]

Now I am almost there! However, my code fails when I get a long vector such as this one

A = [-0.235567779349634 0.0443734431438457 0.0673139255270513 0.340252309954078 -0.755041785819389 -0.421801423658511 0.260198459512273 1.72266328572645 0.163555548444827 1.07704698633001 -0.593017908316194 0.920129574509978 -0.631003190051158 -1.56383039316718 -1.24263419056043 0.847588100277774 0.358464011976733 1.18216087219812]

As far as I can see, the answer should be row = 1, col = 7, numrows = 1, numcols = 6 and summa = 3,5506 (approximately). However my code gives me row = 1, col = 7, numrows = 1, numcols = 12 and summa 2.5013 (approximately). My code is now like this:

function [row,col,numrows,numcols,summa] = maxsubsum(A)
[row, col] = size(A);
maxSoFar = -Inf;
rForMax = [];
cForMax = [];
for r = 1:row
    for c = 1:col
        B = A(r:end, c:end);
        maxVal = sum(sum(B));
        if maxVal > maxSoFar
            maxSoFar = maxVal;
            rForMax = r;
            cForMax = c;
            [p,q] = size(B);
        end
    end
end
maxSoFar2 = -Inf;
rForMax2 = [];
cForMax2 = [];
for r = 1:row
    for c = 1:col
        D = A(r:end, c:end);
        maxVal2 = sum(sum(D));
        if maxVal2 > maxSoFar2
            maxSoFar2 = maxVal2;
            rForMax2 = r;
            cForMax2 = c;
            [m,n] = size(D);
        end
    end
end
if maxSoFar >= maxSoFar2
    row = rForMax;
    col = cForMax;
    numrows = p;
    numcols = q;
    summa = maxSoFar;
elseif maxSoFar < maxSoFar2
    row = rForMax2;
    col = cForMax2;
    numrows = n;
    numcols = m;
    summa = maxSoFar2;
end
end

[charlotte88]

So I figured out my problem with the code, but not how to solve it. All my submatrices starts or ends in a corner, so I need to find a way where a submatrice e.g. can start in column 4 and end in column 6 or something.