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.
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)
Lets say we have s x t matrix (s columns and t rows).
int res = 0;
if(s >= n)
{
for (int r = 0; r < t; ++r) // for each row
{
for (int i = 0; i <= s-n; ++i) //moving through the row
{
int mul = m[i][0];
for (int j = 1; j < n; ++j) //calculating product in a row
{
mul*=m[i][j];
}
if(mul > res)
{
res = mul;
//save i, j here if needed
}
}
}
}
if(t >= n)
{
for (int c = 0; c < s; ++c) // for each column
{
for (int i = 0; i <= t-n; ++i) //moving through the column
{
int mul = m[0][i];
for (int j = 1; j < n; ++j) //calculating product in a column
{
mul*=m[j][i];
}
if(mul > res)
{
res = mul;
//save i, j here if needed
}
}
}
}
If you insist on brute-force, then as you said, you need to iterate over all [x,y],
which will be the starting points of the rows.
From these you can iterate over k adjacent elements in all directions.
You can store the directions as vectors in an array.
This would run in O(k n^2).
For n x n matrix and looking for k elements in row, C-like pseudocode would look like this (note there is no bounds checking, for the sake of simplicity):
// define an array of directions as [x,y] unit vectors
// you only need to check in 4 directions, other 4 are the same, just reversed
int[4][2] dirs = {{1,0}, {1,1}, {0,1}, {-1,1}};
// iterate over all starting positions
for (x = 0; x < n; ++x) {
for (y = 0; y < n; ++y) {
// iterate over all directions
for (d = 0; d < 4; ++d) {
result = 1;
// iterate over elements in row starting at [x,y]
// going in direction dirs[d]
for (i = 0; i < k; ++i) {
// multiply current result by the element,
// which is i places far from the beginning [x,y]
// in the direction pointed by dirs[d]
new_x = x + i * dirs[d][0];
new_y = y + i * dirs[d][1];
// you need to check the bounds, i'm not writing it here
// if new_x or new_y are outside of the matrix
// then continue with next direction
result *= matrix[new_x][new_y];
}
if (result > max) {
max = result;
}
}
}
}
Slightly better, less of a brute-force way would be to
start on the boundary of a matrix, pick a direction and go in this direction to the opposite side of the matrix, keeping the product of the last k numbers on the way.
While walking, you keep the product, multiplying it by the number you got to and dividing by the number you left k steps ago.
This way, with some bounds checking of course,
the product is always product of the last k numbers,
therefore if the current product is more than maximum, just let max = product.
This runs always in O(n^2).
