A[n,m]是一个n行m列的矩阵，a[i,j]表示A的第i行j列的元素，定义x[i,j]为A的第i行和第j列除了a[i,j]之外所有元素(共n+m-2个)的乘积，即x[i,j]=a[i,1]*a[i,2]*...*a[i,j-1]*...*a[i,m]*a[1,j]*a[2,j]...*a[i-1,j]*a[i+1,j]...*a[n,j],现输入非负整形的矩阵A[n,m]，求MAX(x[i,j])，即所有的x[i,j]中的最大值。
[编程题]矩阵元素相乘
/**
* 初始化二维数组help[n][m]，每一位都是1。
* 在读到i行j列元素后，将它乘在
* 1. [i][0] - [i][j-1]
* 2. [i][j+1] - [i][m-1]
* 3. [0][j] - [i-1][j]
* 4. [i+1][j] - [n-1][j]
* 上述各个位置。
* 最后求出help数组的最大值即可。
**/
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int m = scan.nextInt();
int[][] help = new int[n][m];
for(int i=0;i<n;i++)
Arrays.fill(help[i], 1);
//计算
for(int i =0;i<n;i++){
for(int j=0;j<m;j++){
int value = scan.nextInt();
int tmp=0;
for(;tmp<i;tmp++)
help[tmp][j]*=value;
for(tmp=i+1;tmp<n;tmp++)
help[tmp][j]*=value;
for(tmp=0;tmp<j;tmp++)
help[i][tmp]*=value;
for(tmp=j+1;tmp<m;tmp++)
help[i][tmp]*=value;
}
}
//获得最大值
int max = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(help[i][j]>max)
max = help[i][j];
}
}
System.out.println(max);
}
scan.close();
}
}
编辑于 2016-08-09 00:51:04
回复(2)
更多回答
//暴力法
#include<iostream>
#include<vector>
using namespace std;
int main(){
int y,q,r,i,j,n,m,max;
while(cin>>n>>m){
vector<vector<int> > p(n,vector<int>(m,0));
max = 0;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
cin >> p[i][j];
for(i=0;i<n;i++){
for(j=0;j<m;j++){
int templ = 1,temph = 1;
for(q=0;q<n;q++)
if(q != i)
templ *= p[q][j];
for(r=0;r<m;r++)
if(r != j)
temph *= p[i][r];
if( templ * temph > max )
max = templ * temph;
}
}
cout << max << endl;
}
return 0;
}
//第一次按行遍历，若行中有零，只计算0处的值。若无零。各处行值为 行总值/该点值。
//第二次按列遍历，若列中有零，只计算0处的列值*行值，若无0各处列值 列总值/该点值
#include<iostream>
#include<vector>
using namespace std;
int main(){
int y,q,r,i,j,n,m,max;
while(cin>>n>>m){
vector<vector<int> > p( n,vector<int>(m,0) ),h( n,vector<int>(m,1));
max = 0;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
cin >> p[i][j];
}
}
for(i=0;i<n;i++){
int temph = 1;
for(int k=0;k<m;k++)
temph *= p[i][k];
for(j=0;j<m;j++){
if( temph == 0 ){
if( p[i][j] == 0 ){
for(r=0;r<m;r++)
if(r != j)
h[i][j] *= p[i][r];
}
else
h[i][j] = 0;
}
else{
h[i][j] = temph/p[i][j];
}
}
}
for(i=0;i<m;i++){
int templ = 1;
for(int k=0;k<n;k++)
templ *= p[k][i];
for(j=0;j<n;j++){
int templl = 1;
if( templ == 0 ){
if( p[j][i] == 0 ){
for(r=0;r<n;r++)
if(r != j)
templl *= p[r][i];
if(templl*h[j][i]>max)
max = templl*h[j][i];
}
}
else{
templl = templ/p[j][i];
if(templl*h[j][i]>max)
max = templl*h[j][i];
}
}
}
cout << max << endl;
}
return 0;
}
编辑于 2017-07-26 17:35:49
回复(0)
//用了两个辅助数组，分别记录每行和每列的乘积，遇到0时直接计算，当0比较少时， //复杂度为O(n*m) #include<iostream> #include<vector> using namespace std; int main(){ int n,m; int table[100][100]; while(cin>>n>>m) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>table[i][j]; int *a = new int[n]; int *b = new int[m]; for(int i=0;i<n;i++) { a[i] = 1; for(int j=0;j<m;j++) a[i] *= table[i][j]; } for(int i=0;i<m;i++) { b[i] = 1; for(int j=0;j<n;j++) b[i] *= table[j][i]; } int result = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { int temp = 1; if(table[i][j]==0) { for(int k=0;k<n;k++) { if(k==i) continue; temp *= table[k][j]; } for(int k=0;k<m;k++) { if(k==j) continue; temp *= table[i][k]; } } else temp = a[i] * b[j] / table[i][j] /table[i][j]; if(temp>result) result = temp; } cout<<result<<endl; } return 0; }
编辑于 2017-03-28 22:37:27
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m){
vector<vector<int>> a(n, vector<int>(m, 0));
for(int i = 0; i < n; i++)
for(int j = 0; j< m; j++)
cin>>a[i][j];
long res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j< m; j++){
long sum = 1;
for(int row = 0; row < n; row++){
if(row == i)
continue;
sum = sum*a[row][j];
}
for(int col = 0; col < m; col++){
if(col==j)
continue;
sum = sum*a[i][col];
}
res = max(res, sum);
}
}
cout<<res<<endl;
}
return 0;
}
发表于 2016-06-14 15:33:49
回复(0)
// 首先保存所有的行列的元素的乘积，由于存在零，因此可以把为零的元素设置为-1
// 时间复杂度O(n*m),空间复杂度O(n+m)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[][] num = new int[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
num[i][j] = sc.nextInt();
if(num[i][j]<=0){
num[i][j] = -1;
}
}
long[] row = new long[n];
long[] col = new long[m];
for(int i=0;i<n;i++){
row[i] = 1;
for(int j=0;j<m;j++){
row[i] *= num[i][j];
}
}
for(int i=0;i<m;i++){
col[i] = 1;
for(int j=0;j<n;j++){
col[i] *= num[j][i];
}
}
long max = (row[0]/num[0][0])*(col[0]/num[0][0]);
long t;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
t = (row[i]/num[i][j])*(col[j]/num[i][j]);
if(max<t)
max = t;
}
System.out.println(max);
}
}
}
发表于 2017-09-07 10:34:06
回复(0)
暴力法就可以AC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine()) != null){
String[] params = line.trim().split(" ");
int m = Integer.parseInt(params[0]);
int n = Integer.parseInt(params[1]);
int[][] arr = new int[m][n];
for(int i = 0; i < m; i++){
String[] row = br.readLine().split(" ");
for(int j = 0; j < n; j++)
arr[i][j] = Integer.parseInt(row[j]);
}
int max = Integer.MIN_VALUE;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int startRow = 0, startCol = 0, temp = 1;
for(; startRow < i; startRow++)
temp *= arr[startRow][j];
startRow ++;
for(; startRow < m; startRow++)
temp *= arr[startRow][j];
for(; startCol < j; startCol++)
temp *= arr[i][startCol];
startCol ++;
for(; startCol < n; startCol++)
temp *= arr[i][startCol];
max = Math.max(max, temp);
}
}
System.out.println(max);
}
}
}
发表于 2021-07-15 18:31:50
回复(0)
同样是用了2个辅助数组row和col记录每行和每列的乘积;
比较骚的是在读取数据时，遇到输入为0直接换成-1即可
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m;
while (cin >> n >> m){
vector<vector<int>> A(n, vector<int>(m, 0));
vector<int> row(n);
vector<int> col(m);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> A[i][j];
A[i][j] = A[i][j] == 0 ? -1 : A[i][j];
row[i] = j==0 ? A[i][j] : row[i] * A[i][j];
col[j] = i==0 ? A[i][j] : col[j] * A[i][j];
}
}
int res = 0;
//cout << col[2] << endl;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
res = max(res, row[i] * col[j] / A[i][j] / A[i][j]);
}
}
cout << res << endl;
}
return 0;
}
发表于 2021-05-28 19:49:51
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{ int n,m; while(cin>>n>>m){ vector<vector<int> > a(n,vector<int>(m,0)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j]; long long r = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { long long s = 1; for(int p=0;p<n;p++) { if(p==i) continue; s *= a[p][j]; } for(int q=0;q<m;q++) { if(q==j) continue; s *= a[i][q]; } r = max(r,s); } cout<<r<<endl; } return 0;
}
发表于 2017-11-13 13:44:01
回复(0)
写的有点长！！
#include<iostream>
#include<vector>
using namespace std;
int Multiply(vector<vector<int>> &res,int m,int n,int i,int j)
{
int val=1;
for(int k=0;k<m;k++)
{
if(k!=i)
val*=res[k][j];
}
for(int k=0;k<n;k++)
{
if(k!=j)
val*=res[i][k];
}
return val;
}
int findMax(vector<vector<int>> &res,int m,int n) //m行n列的矩阵！
{
vector<vector<int> > Max(m,vector<int>(n));
vector<int> row(m,1);
vector<int> col(n,1);
for(int i=0;i<m;i++)
{
//row[i]=1;
for(int j=0;j<n;j++)
row[i]*=res[i][j];
}
for(int i=0;i<n;i++)
{
//row[i]=1;
for(int j=0;j<m;j++)
col[i]*=res[j][i];
}
int maxval=-1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(res[i][j])
Max[i][j]=(row[i]*col[j])/(res[i][j]*res[i][j]);
else
Max[i][j]=Multiply(res,m,n,i,j);
if(Max[i][j]>maxval)
maxval=Max[i][j];
}
}
return maxval;
}
int main()
{
int m,n;
while(cin>>m>>n)
{
vector<vector<int> > res(m,vector<int>(n));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
cin>>res[i][j];
}
cout<<findMax(res,m,n)<<endl;
}
return 0;
}
发表于 2017-06-26 15:22:31
回复(0)
方法比较老土，但在Eclipse中运行正确。
代码如下
import java.util.Scanner;
public class TestArrayMaxMulti
{/*题目描述
A[n,m]是一个n行m列的矩阵，
a[i,j]表示A的第i行j列的元素，
定义x[i,j]为A的第i行和第j列除了a[i,j]之外所有元素(共n+m-2个)的乘积，
即x[i,j] = a[i,1]*a[i,2]*...*a[i-1,j]*a[i+1,j]...*a[n,j],
现输入非负整形的矩阵A[n,m]，求MAX(x[i,j])，即所有的x[i,j]中的最大值*/
private int row = 0;//行数
private int col = 0;//列数
@SuppressWarnings("resource")
public int[][] initArray()
{
System.out.print("请输入矩阵行数 :");
Scanner _inRow = new Scanner(System.in);
row = _inRow.nextInt();
System.out.print("请输入矩阵列数 :");
Scanner _inCol = new Scanner(System.in);
col = _inCol.nextInt();
int[][] a = new int[row][col];
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
Scanner _in = new Scanner(System.in);
a[i][j] = _in.nextInt();
}
System.out.println();
}
return a;
}
public int multiOfEach(int[][] a, int m, int n)
{//计算每次的乘积
int temp = 1;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
if(i == m)
{
temp *= a[i][j];//a[m][n]所在m行的乘积
}
}
}
for(int j = 0; j < col; j++)
{
for(int i = 0; i < row; i++)
{
if(j == n)
{
temp *= a[i][j];
}
}
}
//a[m][n]计算了两次乘积,除去
temp = temp/(a[m][n]*a[m][n]);
return temp;
}
public int check(int[][] a)
{//循环检验
int result = Integer.MIN_VALUE;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
int value = this.multiOfEach(a, i, j);
if(value > result)
{//比较与赋值
result = value;
}
}
}
System.out.println(result);
return result;
}
public static void main(String[] args)
{
TestArrayMaxMulti t =
new TestArrayMaxMulti();
t.check(t.initArray());
}
}
截图如下 
发表于 2016-09-05 12:56:28
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int m = in.nextInt();
int[][] a = new int[n][m];
int max = -1;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
a[i][j] = in.nextInt();
}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
int r = getMax(a,i,j);
if(r>max)
max = r;
}
}
System.out.println(max);
}
}
public static int getMax(int[][] a,int I,int J){
int max = 1;
for(int i = 0;i<a.length;i++){
if(i==I)
continue;
max *= a[i][J];
}
for(int j = 0;j<a[0].length;j++){
if(j==J)
continue;
max *= a[I][j];
}
return max;
}
}
发表于 2016-04-13 19:49:51
回复(0)
//自己看吧 //row_result[i][j]保存第i行第j列那个数所在行除了他本身以外的乘积 //col_result[i][j]保存第i行第j列那个数所在列除了他本身以外的乘积 //这个求解过程是优化的 //如果你知道leetcode有道题：Product of Array Except Self#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <ctime>#include <cstring>#include <vector>#include <queue>#include <map>#include <set>#include <unordered_map>using namespace std;#define INT_MIN -2147483647intmain(void){intm;intn;vector<vector<int> > v;inttemp;while(cin >> m >> n){v.clear();for(inti = 0; i<m; i++){vector<int> v1;for(intj = 0; j<n; j++){cin >> temp;v1.push_back(temp);}v.push_back(v1);}vector<vector<int> > row_result(m, vector<int>(n, 1));for(inti = 0; i<m; i++){for(intj = n - 2; j >= 0; --j)row_result[i][j] = row_result[i][j + 1] * v[i][j + 1];intleft = 1;for(intj = 0; j < n; ++j){row_result[i][j] *= left;left *= v[i][j];}}vector<vector<int>> col_result(m, vector<int>(n, 1));for(intj = 0; j<n; j++){for(inti = m - 2; i >= 0; --i)col_result[i][j] = col_result[i + 1][j] * v[i + 1][j];inttop = 1;for(inti = 0; i < m; ++i){col_result[i][j] *= top;top *= v[i][j];}}intmax = INT_MIN;for(inti = 0; i < m; i++){for(intj = 0; j < n; j++){if(max < row_result[i][j] * col_result[i][j])max = row_result[i][j] * col_result[i][j];}}cout << max << endl;}return0;}
编辑于 2015-10-22 21:03:11
回复(0)
//时间复杂度o(m*n),DP动态规划，没有用除法，可有效防止除0异常
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
vector<vector<int> > vec(n,vector<int>(m,0)),p1(n,vector<int>(m,1)),p2(n,vector<int>(m,1));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>vec[i][j];
if(j>0)
p1[i][j]=p1[i][j-1]*vec[i][j-1];
if(i>0)
p2[i][j]=p2[i-1][j]*vec[i-1][j];
}
int temp;
for(int i=0;i<n;i++){
temp=1;
for(int j=m-1;j>=0;j--){
p1[i][j]=p1[i][j]*temp;
temp*=vec[i][j];
}
}
for(int i=0;i<m;i++){
temp=1;
for(int j=n-1;j>=0;j--){
p2[j][i]=p2[j][i]*temp;
temp*=vec[j][i];
}
}
int max=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(p1[i][j]*p2[i][j]>max)
max=p1[i][j]*p2[i][j];
cout<<max<<endl;
}
return 0;
}
编辑于 2016-08-25 15:31:23
回复(4)
while True: try: n,m = map(int,input().split()) except: break a = [] for i in range(n): b = list(map(int,input().split())) a.append(b) ma = 0 for i in range(n): for j in range(m): c = a[i][:j]+a[i][j+1:] d = [x[j] for x in a] d = d[0:i]+d[i+1:] result = 1 for e in c: result = result*e for f in d: result = result*f if ma< result: ma =result print(ma)
编辑于 2018-08-26 18:55:32
回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
{
int a[100][100];
int maxa=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int temp1=1,temp2=1,temp3;
for(int k=0;k<n;k++)
if(k!=i)
temp1=temp1*a[k][j];
for(int s=0;s<m;s++)
if(s!=j)
temp2=temp2*a[i][s];
temp3=temp1*temp2;
maxa=max(maxa,temp3);
}
}
cout<<maxa<<endl;
}
}
发表于 2017-08-02 14:53:19
回复(0)
while True:
try:
n , m = map(int,input().split())
matrx = []
for i in range(n):
a = list(map(int,input().split()))
matrx.append(a)
dp = []
for i in range(n):
dp.append([])
for j in range(m):
dp[i].append(0)
for i in range(n):
for j in range(m):
prod = 1
for k in range(n):
for l in range(m):
if (k == i or l == j) and (k == i and l == j) == False:
prod *= matrx[k][l]
dp[i][j] = prod
maxi = 0
for i in range(n):
for j in range(m):
maxi = max(maxi , dp[i][j])
print(maxi)
except:
break
发表于 2023-04-16 16:24:40
回复(0)
//直接暴力求解就可以通过，不过感觉可以有更快速地方法
#include <iostream>
#include <vector>
using namespace std;
int getX(const vector<vector<int>> &A, int x, int y)
{
int result=1;
for(int i=0; i<A[0].size(); i++)
{
if(i==y){ continue;}
result *= A[x][i];
}
for(int j=0; j<A.size(); j++)
{
if(j==x){ continue;}
result *= A[j][y];
}
return result;
}
int main() {
int n, m;
while(cin >> n >> m)
{
vector<vector<int>> A(n, vector<int>(m));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin >> A[i][j];
}
}
int max=0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
int x = getX(A, i, j);
if(max<x){ max=x;}
}
}
cout << max << endl;
}
}
// 64 位输出请用 printf("%lld")
发表于 2022-11-02 23:10:25
回复(0)
matlab 暴力题解
try
while 1
a = input('','s'); as = strsplit(a);m=str2num(as{1});n=str2num(as{2});
ma = zeros(m,n);ma2=zeros(m,n);
for i = 1:m
ma(i,:) = str2num(input('','s'));
end
for i = 1:m
for ii = 1:n
hang = ma(i,:);hang(:,ii) =[];hang = prod(hang);
lie = ma(:,ii);lie(i,:) =[];lie = prod(lie);
ma2(i,ii)=hang*lie;
end
end
fprintf("%d\n",max(max(ma2)))
end
cateh
end
发表于 2022-03-28 15:38:23
回复(0)
def fun(A, n, m):
a = [[0 for j in range(m)] for i in range(n)]
for i in range(n): # row
for j in range(m): # col
sum = 1
# discuss col
for x in range(m):
if x == j:
continue
sum *= A[i][x]
# discuss row
for y in range(n):
if y == i:
continue
sum *= A[y][j]
a[i][j] = sum
return max([max(x) for x in a])
while True:
try:
n,m = list(map(int,input().split()))
except:
break
data = []
for i in range(n):
data.append(list(map(int,input().split())))
print(fun(data,n,m))
编辑于 2022-03-03 20:52:22
回复(0)
必须得吐槽，解决了除0问题后run半天还是错，原来是一组输入有多个测试用例？？？
题目里面没有给出说要一组输入多个测试用例，然后输出没错误提示真的没法改...
然后其实O(n^3)也能过？
while True:
try:
n,m=map(int, input().strip().split())
A=[] #A存储当前矩阵
for _ in range(n):
tmp=list(map(int, input().strip().split()))
A.append(tmp)
d={} #d存储列信息
for i in range(n):
for j in range(m):
if j not in d:d[j]=[A[i][j]]
else:d[j]+=[A[i][j]]
ans=0
for i in range(n):
for j in range(m):
c=1
for x in range(len(A[i])):
if x!=j:
c*=A[i][x]
for y in range(len(d[j])):
if y!=i:
c*=A[y][j]
ans=max(ans,c)
print(ans)
except:
break
发表于 2021-08-11 16:16:13
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-20 17:19:23 -
2022-09-15 23:35:43 -
2022-09-15 14:06:06 -
2022-09-13 23:44:27
-
2022-09-13 23:23:55
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
