int max_value(int *line, int len) {
int max = 0, top = -1;
int stack[len], right[len], left[len];
for (int i = 0; i < len; i++) {
while (top >= 0 && line[i] < line[stack[top]]){
right[stack[top]] = i;
if (top > 0) {
left[stack[top]] = stack[top-1];
}
else {
left[stack[top]] = -1;
}
top--;
}
top++;
stack[top] = i;
}
while (top >= 0) {
right[stack[top]] = len;
if (top > 0) {
left[stack[top]] = stack[top-1];
}
else {
left[stack[top]] = -1;
}
top--;
}
for (int j = 0; j < len; j++) {
max = fmax(max, (right[j] - left[j] -1) * line[j]);
}
return max;
}
int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize){
int max = 0;
int *new_matrix= calloc(matrixColSize[0], sizeof(int));
for (int i = 0; i < matrixSize; i++) {
for (int j = 0; j < matrixColSize[0]; j++) {
if (matrix[i][j] != '0') {
new_matrix[j]+=(matrix[i][j] - '0');
}
else {
new_matrix[j] = 0;
}
}
max = fmax(max, max_value(new_matrix, matrixColSize[0]));
}
return max;
}
暂无评论