Find the indices of elements of matrix that form the maximum product

Question

I have a task to find the maximum product of elements in a matrix. The input arguments are the matrix and the scalar n that tells me how many elements to multiply. If n=2, then I should multiply two by two. The maximum product can lie either in rows, or in columns on in diagonal. For example in this case A's elements were multiplied 2 by 2 along rows (B) and columns (C).

A =
   8     1     6
   3     5     7
   4     9     2
B =
      8.0000    6.0000
     15.0000   35.0000
     36.0000   18.0000
C =
     24.0000    5.0000   42.0000
     12.0000   45.0000   14.0000

I do it using the loop

    c=[]
for ii = 1:(length(A)-n+1)
    p = prod(A(:,ii:ii+n-1));
    c=[c p];
end

or

for i=1:size(A,2)
      B(i,:)=real(exp(conv(log(A(i,:)),ones(1,n),'valid')));
      C(:,i)=real(exp(conv(log(A(:,i)),ones(1,n),'valid')));
end

In both cases I receive the product but when it comes to getting the maximum among that products, (in my case that is the product of A(2,2)*A(3,2)=45) I cannot find the indices of original matrix elements that formed that product, i.e. (2,2) and (3,2).

Any help will be appreciated.

How does this work for N=3? Would you take B and then multiply across rows and columns to form BB =[48 525 648] and BC = [120 210; 540 630]? Or do you go back to the original matrix? — Ian Riley, Sep 15 '16 at 12:16
No we start always from original A matrix. The `n` is an input argument and it shows the number of elements I should take for multiplication. In case `n=3` we get `B =48.0000 105.0000 72.0000` and `C =96.0000 45.0000 84.0000` In this case the max is 105 which is the product of `A(3,1)*A(3,2)*A(3,3)` — esem, Sep 15 '16 at 12:30
Last bits of clarification; let's say your input is the row vector [2 2 1 2]. Is the correct answer for n=3 4, or is it 8? [Do the numbers need to be in a line?]. If the input is [1 0; 0 1] is the answer for n=2 0? You seem to only multiply through rows or columns, but this doesn't necessarily yield the maximum product in the matrix — Ian Riley, Sep 15 '16 at 13:56
for row vector [2 2 1 2] and n=4 the answer is 8 and there is no column product. My input will be a matrix. If the input is [1 0; 0 1] and n=2 the answer is 0 . I need not the max product but the indices that formed that product. — esem, Sep 15 '16 at 14:23
You may want to look [here](http://stackoverflow.com/questions/39315814/iterate-over-diagonal-elements-of-a-matrix-in-matlab/39336063#39336063) on a similiar task. — EBH, Sep 20 '16 at 07:11

Dave · Answer 1 · 2016-09-16T07:10:23.740

The information can be worked out from knowing where, in B or C, the maximum value occurs. This is returned by the max function as a second argument, albeit in index form. I've tried out your code for producing B and C, and it doesn't seem to produce what you've got, HOWEVER, assuming that you've got some way of producing B and C as in the first part of your question, the following code will return (r1,c1) and (r2,c2) the reference to the two multiplicands (assuming that there is only one maximum - you really do need to check for this):

[maxB,IB]=max(B(:));
[maxC,IC]=max(C(:));
if (maxB>maxC)
    [r1,c1]=ind2sub(size(B),IB);
    r2=r1; c2=c1+n-1;
else
    [r1,c1]=ind2sub(size(C),IC);
    r2=r1+n-1; c2=c1;
end

I'm not quite sure whether n is a distance, in which case:

B=A(:,1:end-n+1).*A(:,n:end);
C=A(1:end-n+1,:).*A(n:end,:);

or whether you mean to take the product of all terms within n of the starting point. Either way, the maximum can be found using the above code.

The answer is good but only adapted to `n=2`. The n is an input argument and it shows the number of elements I should take for multiplication. In case `A=[ 8 1 6;3 5 7;4 9 2]` and `n=3` I get `B =48.0000 105.0000 72.0000` and `C =96.0000 45.0000 84.0000` In this case the max is 105 which is the product of `A(3,1)*A(3,2)*A(3,3)` — esem, Sep 15 '16 at 12:13
That's a fair point! To deal with n>2, change the two commands within the if statement to `c2=c1+n-1` in the first condition, and `r2=r1+n-1` in the else clause. — Dave, Sep 15 '16 at 12:19

score 1 · Answer 2 · answered Sep 15 '16 at 17:04

Given inputs A and n, and assuming you don't care which output you give in case of a tie,

%Setup
[r, c] = size(A)
if r <= n
    maxProd = prod(A(1:n,1),1);
elseif c <= n
    maxProd = prod(A(1,1:n),2);
else 
    return
end

indOut = zeros(n, 2);
dirOut = 0;

%Check verticals 
for ii = 1:(r-n+1)
    for jj = 1:c
         testProd = prod(A(ii:ii+n-1,jj),1);
         if testProd > maxProd
             maxProd = testProd;
             indOut(1,:) = [ii jj];
             dirOut = 1;
         end
    end
end

%Check horizontals
for ii = 1:r
    for jj = 1:(c-n+1)
         testProd = prod(A(ii,jj:jj+n-1),2);
         if testProd > maxProd
             maxProd = testProd;
             indOut(1,:) = [ii jj];
             dirOut = 2;
         end
    end
end

%Set output
for ii = 2:n
    if dirOut == 1;
        indOut(1,n) = indOut(1,n-1) + 1;
    else
        indOut(2,n) = indOut(2,n-1) + 1;
    end
end

If you do care about ties, you'll have to add additional outputs to the side of the indOut matrix

Find the indices of elements of matrix that form the maximum product

2 Answers2