A maximum submatrix problem. A brute-force
solution wouldn’t get TLE. My C
rank-4624 implementation:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX(X, Y) (X > Y) ? X : Y
#define MIN(X, Y) (X < Y) ? X : Y
#define N 101
int array[N][N], n;
int main() {
int x, y, x2, y2, val, max = INT_MIN;
scanf("%d", &n);
for (y = 0; y < n; ++y) {
for (x = 0; x < n; ++x) {
scanf("%d", &val);
array[y][x] = val;
if (x > 0)
array[y][x] += array[y][x - 1];
if (y > 0)
array[y][x] += array[y - 1][x];
if (y > 0 && x > 0)
array[y][x] -= array[y - 1][x - 1];
max = MAX(max, array[y][x]);
}
}
for (y = 0; y < n; ++y) {
for (x = 0; x < n; ++x) {
for (y2 = y; y2 < n; ++y2) {
for (x2 = x; x2 < n; ++x2) {
max = MAX(max, array[y2][x2] - array[y2][x] - array[y][x2] + array[y][x]);
}
}
}
}
printf("%d\n", max);
return 0;
}
Another
solution is done via Kadane’s Algorithm which is DP. This is what’s acutually required by the problem setter. With Kadane’s Algorithm able to solve a 1D/array problem, we need to reduce the 2D/matrix problem at hand to a 1D problem.
- As you might have guessed, this reduction is easily made with prefix/cumulative sum. We simply add the value of each row to all the following ones. This is done simultaneously along taking input.
- Combine each two rows and do the Kadane
algorithm.
- Done!
My C
implementation:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX(X, Y) (X > Y) ? X : Y
#define POS(X) MAX(X, 0)
#define N 101
int matrix[N][N], n, maxSum = INT_MIN;
int kadane(int* row, int len) {
int x, sum;
for (x = 0, sum = POS(row[0]); x < len; ++x, sum = POS(sum + row[x]))
maxSum = MAX(sum, maxSum);
return maxSum;
}
int kadane2(int* row1, int* row2, int len) {
int x, sum;
for (x = 0, sum = POS(row2[0] - row1[0]); x < len; ++x, sum = POS(sum + row2[x] - row1[x]))
maxSum = MAX(sum, maxSum);
return maxSum;
}
int main() {
int x, y, y2;
/*input*/
scanf("%d", &n);
for (x = 0; x < n; ++x)
scanf("%d", &matrix[0][x]);
for (y = 1; y < n; ++y) {
for (x = 0; x < n; ++x) {
scanf("%d", &matrix[y][x]);
matrix[y][x] += matrix[y - 1][x];
}
}
/*solve*/
for (y = 0; y < n; ++y) {
kadane(matrix[y], n);
for (y2 = y + 1; y2 < n; ++y2)
kadane2(matrix[y], matrix[y2], n);
}
/*result*/
printf("%d\n", maxSum);
return 0;
}
Rank 253. Worth it?