計算するための答えを見つけましたO(mn)-まだ少し事前計算があります-しかし、今回は最後のものも簡単O(mn.log(mn))です.すべての行列の値のリストを並べ替えるだけです.
事前計算:
最初のステップは、行列の値の整然とした構造を単純に構築することです。たとえばM(A)、 を使用<algorithm>std::sortして、その構造を順序付けます。
任意のサブマトリックスの最大値を取得(a,b):
行列の最大値を取得するには、事前に計算された構造から最大のものから始めて、M(A)それが 内にあるかどうかを確認します(a,b)。
- もしそうなら、あなたは終わった
- そうでなければ、次のものを取ります
M(A)
マトリックス.h
#ifndef myMatrix_JCHO
#define myMatrix_JCHO
typedef unsigned int u_it;
typedef std::pair<u_it, u_it> uup;
class Matrix
{
public:
Matrix(u_it _n, u_it _m);
Matrix(const Matrix& matr);
Matrix& operator=(const Matrix& matr);
~Matrix();
u_it getNumRows() ;
u_it getNumCols() ;
int getC(u_it i, u_it j);
void setC(u_it i, u_it j, int v);
void printMatrix();
int maxSub(u_it a_i, u_it a_j, u_it b_k, u_it b_l);
private:
u_it n, m;
int **pC;
};
#endif
マトリックス.cpp
#include <iostream>
#include <string>
#include <sstream>
#include "matrix.h"
Matrix::Matrix(u_it _n, u_it _m) {
n=_n;
m=_m;
//int k=0;
pC = new int*[n];
for (u_it i=0; i<n; ++i){
pC[i]=new int[m];
for(u_it j=0; j<m; ++j){
pC[i][j]=rand()%1000;
}
}
}
Matrix::~Matrix(){
for (u_it i=0; i<n; ++i){
delete [] pC[i];
}
delete [] pC;
std::cout << "matrix destroyed\n";
}
u_it Matrix::getNumRows() {
return n;
}
u_it Matrix::getNumCols() {
return m;
}
int Matrix::getC(u_it i, u_it j){
return pC[i][j];
}
void Matrix::setC(u_it i, u_it j, int v){
pC[i][j]=v;
}
void Matrix::printMatrix(){
for (u_it i=0; i<n; ++i){
std::cout << "row " <<i<<" [ ";
for(u_it j=0; j<m; ++j){
std::cout << pC[i][j] << '\t';
}
std::cout << "]\n";
}
}
main.cpp
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>
#include "matrix.h"
// sort function for my vector of pair:
bool oMyV(std::pair<uup, int> x, std::pair<uup, int> y) { return (x.second > y.second); }
// check that p is within matrix formed by a and b
bool isIn_a_b(uup p, uup a, uup b){
bool res = false;
if (p.first >= a.first && p.first <= b.first) {
if (p.second >= a.second && p.second <= b.second) {
res = true;
}
}
return res;
}
int main() {
u_it n_rows, n_cols;
std::cout << " enter number of rows:";
std::cin >> n_rows;
std::cout << " enter number of cols:";
std::cin >> n_cols;
std::cout << " pre-computing...\n";
std::pair<uup, int> *ps;
std::vector<std::pair<uup, int> > myV;
Matrix * mat=new Matrix(n_rows,n_cols);
// print to debug:
mat->printMatrix();
// "PRE" computation
for (u_it i=0; i<n_rows; ++i) {
for (u_it j=0; j<n_cols; ++j) {
ps=new std::pair<uup, int>(std::make_pair(i,j), mat->getC(i,j));
myV.push_back(*ps);
}
}
std::sort(myV.begin(), myV.end(), oMyV);
/* in case you want to print ordered valuet ordered valuess for debug */
for (std::vector<std::pair<uup, int> >::iterator it=myV.begin(); it!=myV.end(); ++it) {
std::cout << it->second << " at [" << it->first.first <<','<<it->first.second<< "]\n";
}
/**/
// call to values
bool byebye=false;
uup a, b;
do {
std::cout << " enter i,:"; std::cin >> a.first;
std::cout << " enter j,:"; std::cin >> a.second;
std::cout << " enter k,:"; std::cin >> b.first;
std::cout << " enter l,:"; std::cin >> b.second;
std::vector<std::pair<uup, int> >::iterator it=myV.begin();
std::cout << " a:["<<a.first<<','<<a.second<<"]-b:["<<b.first<<','<<b.second<<"] in ";
std::cout << " M:[0,0]--:["<<n_rows-1<<','<<n_cols-1<<"]\n";
// check validity:
if ( isIn_a_b(a, std::make_pair(0,0), std::make_pair(n_rows-1, n_cols-1) )
&& isIn_a_b(b, std::make_pair(0,0), std::make_pair(n_rows-1, n_cols-1) )
&& (a.first <= b.first)
&& (a.second <= b.second)
) {
while (! isIn_a_b(it->first, a, b) && it!=myV.end()){
++it;
}
std::cout << "Found:" << it->second << " at [" << it->first.first <<','<<it->first.second<< "]\n";
} else {
std::cout << "makes no sense. bye.\n";
byebye=true;
}
} while (!byebye);
}
メイクファイル
(忘れないでください: Makefile で集計します)
OBJS = matrix.o main.o
CC = g++ -std=c++0x
DEBUG = -g
CFLAGS = -std=c++0x -Wall -c $(DEBUG)
LFLAGS = -std=c++0x -Wall $(DEBUG)
TARFILE = ${HOME}/jcho/good/matrix.tar
p1 : $(OBJS)
$(CC) $(LFLAGS) $(OBJS) -o p1
matrix.o: matrix.cpp matrix.h
$(CC) $(CFLAGS) matrix.cpp
main.o: main.cpp matrix.h
$(CC) $(CFLAGS) main.cpp
clean:
\rm -f *.o *~ p1
tar:
tar cfv $(TARFILE) *.h *.cpp Makefile \
p1 && \
echo "tar $(TARFILE) created successfuly."