c++ - 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

如果您坚持蛮力，那么正如您所说，您需要遍历 all [x,y]，这将是行的起点。从这些你可以迭代k所有方向的相邻元素。您可以将方向作为向量存储在数组中。这将运行在O(k n^2).

对于n x n矩阵并k在行中查找元素，类似 C 的伪代码如下所示（注意，为了简单起见，没有边界检查）：

// 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;
            }
        }
    }
}

稍微好一点，不那么暴力的方法是从矩阵的边界开始，选择一个方向，然后沿着这个方向走到矩阵的另一侧，保持最后一个k数字的乘积。

走路时，你保留产品，乘以你得到的数字并除以你离开k前几步的数字。这样，当然有一些边界检查，乘积总是最后一个k数字的乘积，因此如果当前乘积大于最大值，就让max = product. 这总是在O(n^2).

Answer 2

假设我们有 sxt 矩阵（s 列和 t 行）。

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
            }
        }   
    }   
}

Answer 3

使用滚动乘法查找行中最大产品的版本以节省一些资源。这个滚动过程意味着我们不必将n值相乘来找到这些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;
 }

您也可以完成此操作以处理列：

填充矩阵：

#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);
}

打印矩阵并在行中找到最大产品：

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;
}

用法：

/*
 * 
 */
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;
}

结果：

资源：42

7,2,3,

运行成功（总时间：113ms）