版本可以使用滚动乘法来找到最大乘积，这个滚动过程意味着我们不必乘以 n 值来找到这些 n 值的每个乘积，但是我们只需要执行一个乘法和一个部门：

  if（currN == N）{//计算完整的产品第一次
 while（currn）{
 product * =（* it3 ++）; 
 --currn; 
} 
} else {//滚动计算
 product * =（*（it3 + n  -  1））/（*（it3  -  1） 
 it3 + = n; 
} 
 

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

填充矩阵：

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

 typedef vector<载体， int> >矩阵; 
 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）.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（\\\
）; 
 ++ it; 
} 
} 

 / ** 
 * 
 * @param matrix 
 *使用滚动乘法的行中最大的乘积
 * @param n个因素
 * @param v最大乘积的因子
 * @返回最大乘积
 * / 
 int maximumProductInRow（Matrix& matrix，int n，vector< int>& v）{
 if（n> matrix.size（））return -1; 
 int res = 0; 
 int N = matrix.size（） -  n + 1; //行（或列）中的产品数量
 / *在行中搜索* / 
 outIt it = matrix.begin（）; 
 while（it！= matrix.end（））{
 inIt it2 =（* it）.begin（）; 
 int currN = N; 
 int product = 1; 
 while（currN）{//滚动产品计算
 inIt it3 = it2; 
 int currn = n; 
 if（currN == N）{//计算完整的产品第一次
 while（currn）{
 product * =（* it3 ++）; 
 --currn; 
} 
} else {//滚动计算
 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）{

矩阵4，vector< int>（））; 
 fillMatrix（matrix）; 
 printMatrix（matrix）; 
 vector< int> v（3）; 
 int res = largestProductInRow（matrix，3，v）; 
 printf（res：％d\\\
，res）; 
 copy（v.begin（），v.end（），ostream_iterator< int>（cout，，））; 
 return 0; 
} 
 

结果：

res：42

7,2,3，

RUN SUCCESSFUL（总时间：113ms） p>

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)