Matrix largest product of n numbers in a row

Question

Hello I'm having trouble with a little program I am trying to write. The problem is if I'm given any matrix size (lets just say a 4x4 for this example), find the largest product of n numbers in a row (lets say n = 3). The 3 numbers in a row can be horizontal, vertical, or diagonal. So heres a matrix:

1 1 2 5
1 5 2 4
1 7 2 3
1 8 2 1

If n was equal to 3 then my largest product would be 280 (5*7*8). Now I have my matrix loaded into a 2D vector. I'm not too picky on how the program works(brute force is fine), so far I know I'm going to have to have at least two nested for loops to go through each staring location of the matrix but I haven't been successful in finding the current answer. Any advice will help, thank you.

Answer 1

Version to find max product in rows using rolling multiplication to save some resources. This rolling procedure means that we don't have to multiply n values to find each product of these n values, but instead we have to just do one multiplication and one division:

if (currN == N) { // compute full product first time
    while (currn) {
         product *= (*it3++);
          --currn;
    }
 } else {          // rolling computation
     product *= (*(it3 + n - 1)) / (*(it3 - 1));
     it3 += n;
 }

It is up to you to complete this to handle also columns:

populate matrix:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;

typedef vector< vector< int> > Matrix;
typedef Matrix::iterator outIt;
typedef vector< int>::iterator inIt;

void fillMatrix( Matrix& matrix) {
    outIt it = matrix.begin();
    (*it).push_back( 1);
    (*it).push_back( 1);
    (*it).push_back( 2);
    (*it).push_back( 5);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 5);
    (*it).push_back( 2);
    (*it).push_back( 4);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 7);
    (*it).push_back( 2);
    (*it).push_back( 3);
    ++it;
    (*it).push_back( 1);
    (*it).push_back( 8);
    (*it).push_back( 2);
    (*it).push_back( 1);
}

print matrix and find max product in rows:

void printMatrix( Matrix& matrix) {
    outIt it = matrix.begin();
    while ( it != matrix.end()) {
        inIt it2 = (*it).begin();
        while ( it2 != (*it).end()) {
            printf( "%d", *it2);
            ++it2;
        }
        printf( "\n");
        ++it;
    }
}

/**
 * 
 * @param matrix
 * Largest product in row using rolling multiplication
 * @param n number of factors
 * @param v factors of largest product
 * @return largest product
 */
int largestProductInRow( Matrix& matrix, int n, vector< int>& v) {
    if ( n > matrix.size()) return -1;
    int res = 0;
    int N = matrix.size() - n + 1; // number of products in row (or column)
    /* search in rows */
    outIt it = matrix.begin();
    while (it != matrix.end()) {
        inIt it2 = (*it).begin();
        int currN = N;
        int product = 1;
        while (currN) {       // rolling product calculation
            inIt it3 = it2;
            int currn = n;
            if (currN == N) { // compute full product first time
                while (currn) {
                    product *= (*it3++);
                    --currn;
                }
            } else {          // rolling computation
                product *= (*(it3 + n - 1)) / (*(it3 - 1));
                it3 += n;
            }
            if (product > res) {
                res = product;
                copy(it3 - n, it3, v.begin());
            }
            --currN;
            ++it2;
        }
        ++it;
    }
    return res;
}

usage:

/*
 * 
 */
int main(int argc, char** argv) {

    Matrix matrix( 4, vector< int>());
    fillMatrix( matrix);
    printMatrix( matrix);
    vector< int> v(3);
    int res = largestProductInRow( matrix, 3, v);
    printf( "res:%d\n", res);
    copy( v.begin(), v.end(), ostream_iterator<int>(cout, ","));
    return 0;
}

result:

res:42

7,2,3,

RUN SUCCESSFUL (total time: 113ms)