# UVa 108 Maximum Sum

### 题解

#### 题解 1

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  #include #include #define maxn 100+5 using namespace std; int v, N, sum[maxn][maxn] = {{0}}; void solve() { int MaxSum = -200; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = i; k <= N; k++) { for (int l = j; l <= N; l++) { MaxSum = max(MaxSum, sum[k][l]-sum[i-1][l]-sum[k][j-1]+sum[i-1][j-1]); } } } } cout << MaxSum << endl; } int main(void) { while(cin >> N) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { cin >> v; sum[i][j] = v+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } } solve(); } return 0; } 

#### 题解 2

i = 开始行数
j = 结束行数，有i <= j
k = 列数

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39  #include #include #include #define maxn 100+5 using namespace std; int N, m[maxn][maxn], x[maxn]; int find_max() { int cur_sum=x[0], sum=0; for (int l = 0; l < N; l++) { sum += x[l]; cur_sum = max(sum, cur_sum); if (sum < 0) sum = 0; } return cur_sum; } void solve() { int MaxSum = -200; for (int i = 0; i < N; i++) { memset(x, 0, sizeof(x)); for (int j = i; j < N; j++) { for (int k = 0; k < N; k++) x[k] += m[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 >> m[i][j]; solve(); } return 0; }