相同方向上的四个相邻数字的最大乘积是什么（上，下，左，右或对角）

本文介绍了相同方向上的四个相邻数字的最大乘积是什么（上，下，左，右或对角）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

<pre> #include <iostream> #include <vector> long largestProduct(std::vector<std::vector<int> >arr) { std::vector<long>products; for(int row=0; row<20; row++) { for(int col=0; col<20; col++) { int left=col-4; int right=col+4; int down=row+4; int up=row-4; while(up<0) { up++; } while(down>20) { down--; } if(down-up>=4) { for(up; up<=down-4; up++) { long product=1; int rowCount=up; int rowDist=rowCount+4; for(rowCount; rowCount<rowDist; rowCount++) { product=product*arr[rowCount][col]; } products.push_back(product); } } while(left<0) { left++; } while(right>20) { right--; } if(right-left>=4) { for(left; left<=right-4; left++) { long product=1; int colCount=left; int colDist=colCount+4; for(colCount; colCount<colDist; colCount++) { product=product*arr[row][colCount]; } products.push_back(product); } } down=row+4; up=row-4; left=col-4; right=col+4; while(down>20) { down--; } while(up<0) { up++; } while(left<0) { left++; } while(right>20) { right--; } if(down-up>=4 && right-left>=4) { for(up; up<=down-4; up++) { for(left; left<=right-4; left++) { int rowCount=left; int rowDist=rowCount+4; int colCount=left; int colDist=colCount+4; while(rowCount<rowDist) { long product=1; while(colCount<colDist) { product=product*arr[rowCount][colCount]; rowCount=rowCount+1; colCount=colCount+1; } products.push_back(product); } } } } } } long MAX=0; for(int i=0; i<products.size(); i++) { if(products[i]>MAX) { MAX=products[i]; } } return MAX; } int main() { std::vector< std::vector<int> >arr{ {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8}, {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0}, {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65}, {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91}, {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80}, {24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50}, {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70}, {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21}, {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72}, {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95}, {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92}, {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57}, {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58}, {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40}, { 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66}, {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69}, { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36}, {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16}, {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54}, { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48} }; std::cout<<largestProduct(arr); }

我的尝试： 我试过通过调试但它变得复杂，我知道有一些值不止一次，但我会解决它，现在我的主要问题是我想知道出了什么问题

What I have tried: I have tried by debugging but it gets complicated, I know that there are some values that count more than once but I will solve it, now my main problem is I want to understand what goes wrong

推荐答案

首先看看你在做什么并简化它。你反复做这样的事情： Start by looking at what you are doing and simplifying it. Repeatedly, you do things like this: while(down>20) { down--; }

哪个不需要循环：

Which doesn't need a loop:

if (down > 20) down = 20;

甚至

down = down > 20 ? 20 : down;

会好很多。 然后，你在嵌套循环中嵌套循环，在嵌套循环 - 这很麻烦，也很难遵循，也没有效率。 相反，编写一个函数，将x和y地址作为参数，并返回相邻单元格的总和。这是非常微不足道的（唯一的复杂因素是忽略了边缘效应，但这是明确的代码编写）并且根本不需要循环。 测试它，然后在比较结果的循环中调用它到最后一个最大值，整个代码变得更容易阅读，理解和调试。

would be a lot better. Then, you have nested loops within nested loops, within nested loops- that's messy, and also difficult to follow, as well as being inefficient. Instead, write a function that takes an x and y address as parameters, and which returns the sum of the adjacent cells. That's pretty trivial (the only complications are ignoring edge effects but that is clear code to write) and doesn;t need a loop at all. Test that, and then call it inside a loop comparing the result to the last maximum and the whole code becomes much, much easier to read, understand, and debug.

Quote：

相同方向上的四个相邻数字的最大乘积是什么（上，下，左，右或对角）

What is the greatest product of four adjacent numbers in the same direction(up, down, left, right or diagonally)

看起来你跳得太快了一点编程。 分析问题总是好的：乘法的结果是相同的，无论数字的顺序如何。 所以A * B * C * D = D * C * B * A 这意味着对于任何产品减少，您的产品相同，左右相同。所以你可以放弃并离开。如果你检查4个对角线，它是相同的。 所以通过检查水平，垂直和2对角线，你检查所有。 我认为代码执行所有横向，然后代码执行所有垂直，然后对角线世界更容易编写和检查。

Looks like you jumped to programming a little too fast. It is always good to do an analyze of the problem: result of multiplication is the same, no matter the order of numbers. So A*B*C*D = D*C*B*A This imply that for any product down, you have a product up that is identical, the same for left and right. So you can drop up and left. if you check 4 diagonals, it is the same. So by checking horizontal, vertical and 2 diagonals, you check all. I think that code doing all horizontals, then code doing all verticals and then diagonals world be simpler to write and to check.

long largestProduct(std::vector<std::vector<int> >arr) { // Check horizontal // check vertical // check diagonal }

对于最大值，你不需要使用向量，只需要实际值max 当新产品大于最大值时，将其设为新的最大值。

For the max, you don't need to use a vector, just actual value of max and when a new product is greater than max, make it the new max.