UVA 108: https://uva.onlinejudge.org/external/1/108.pdf
/*Maximum Subarray*/
/*
normal : O(N^4)
best : O(N^3)
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 100+5
using namespace std;
int n, matrix[maxn][maxn], cur_matrix[maxn];
int find_max() {
//calculate maximum subarray each row
int cur_sum = 0, sum = 0;
for (int l = 0; l < n; l++) {
sum += cur_matrix[l];
cur_sum = max(sum, cur_sum);
if (sum < 0) sum = 0;
}
return cur_sum;
}
void ans() {
//compress
int MaxSum = -200;
for (int i = 0; i < n; i++) {
memset(cur_matrix, 0, sizeof(cur_matrix));
for (int j = i; j < n; j++) {
for (int k = 0; k < n; k++) {
cur_matrix[k] += matrix[j][k];
}
MaxSum = max(MaxSum, find_max());
}
}
cout << MaxSum << endl;
}
int main(void) {
while (cin >> n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
ans();
}
return 0;
}
/*Maximum Subarray*/
/*
normal : O(N^4)
best : O(N^3)
*/
#include<cstring>
#include<algorithm>
#define maxn 100+5
using namespace std;
int n, matrix[maxn][maxn], cur_matrix[maxn];
int find_max() {
//calculate maximum subarray each row
int cur_sum = 0, sum = 0;
for (int l = 0; l < n; l++) {
sum += cur_matrix[l];
cur_sum = max(sum, cur_sum);
if (sum < 0) sum = 0;
}
return cur_sum;
}
void ans() {
//compress
int MaxSum = -200;
for (int i = 0; i < n; i++) {
memset(cur_matrix, 0, sizeof(cur_matrix));
for (int j = i; j < n; j++) {
for (int k = 0; k < n; k++) {
cur_matrix[k] += matrix[j][k];
}
MaxSum = max(MaxSum, find_max());
}
}
cout << MaxSum << endl;
}
int main(void) {
while (cin >> n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
ans();
}
return 0;
}
留言
張貼留言