http://community.topcoder.com/stat?c=problem_statement&pm=13035
矩阵棋盘的题,比较典型。可以定两条column夹住,然后上下扫,上下扫过程中有一点DP的东西,这样负责度是o(n^3)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std; class TheMatrix {
public:
int MaxArea(vector <string> board) {
int N = board.size();
int M = board[0].size();
int maxArea = 1;
// fix i, j column
for (int i = 0; i < M; i++) {
vector<char> row(N);
for (int j = i; j < M; j++) {
for (int k = 0; k < N; k++) {
if (j == i) {
row[k] = board[k][j];
} else {
if (board[k][j] == board[k][j - 1])
row[k] = 'X';
}
}
int maxLen = 0;
int len = 0;
for (int k = 0; k < N; k++) {
if (row[k] == 'X') {
len = 0;
} else if (k == 0) {
len = 1;
} else if (k > 0 && row[k] != row[k - 1]) {
len++;
} else {
len = 1;
}
maxLen = max(len, maxLen);
}
int area = maxLen * (j - i + 1);
maxArea = max(area, maxArea);
}
}
return maxArea;
}
};