29.マイクロソフト面接問題:一つのマトリックスの中で最大の二次元マトリックス(要素と最大)を求める
1477 ワード
题目:ひとつの行列の中で最大の2次元の行列(元素と最大)を求めます.次のようになります.
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
の最大値は次のとおりです.
4 5
5 3
要求:(1)アルゴリズムを書く;(2)分析時間の複雑さ;(3)Cでキーコードを書く
分析:
直接二次元配列を巡って、最大の二次元配列を求めればOK
次のようになります.
出力は次のとおりです.
max num: 17 matrix: 4 5 5 3
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
の最大値は次のとおりです.
4 5
5 3
要求:(1)アルゴリズムを書く;(2)分析時間の複雑さ;(3)Cでキーコードを書く
分析:
直接二次元配列を巡って、最大の二次元配列を求めればOK
次のようになります.
#include<iostream>
using namespace std;
int max_matrix(int (*array)[5], int maxx, int maxy, int& posi, int& posj)
{
int max = 0;
int i = 0, j = 0;
while(i < maxx - 1)
{
j = 0;
while( j < maxy - 1)
{
int t = array[i][j] + array[i+1][j] + array[i][j+1] + array[i+1][j+1];
if( max < t)
{
max = t;
posi = i;
posj = j;
}
j ++;
}
i ++;
}
return max;
}
int main()
{
int a[3][5] = {{1,2,0,3,4}, {2,3,4,5,1}, {1,1,5,3,0}};
int i = 0, j = 0;
int max = max_matrix(a, 3, 5, i, j);
cout << "max num: " << max <<endl;
cout << "matrix: " << endl;
cout << a[i][j] << " " << a[i][j+1] << endl;
cout << a[i+1][j] << " " << a[i+1][j+1] << endl;
}
出力は次のとおりです.
max num: 17 matrix: 4 5 5 3