2012年9月4日

UVa 108 - Maximum Sum


#include <stdio.h>

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int i, j, map[150][150], cal[150][150];
    for (i = 1; i <= n; i++)
      for (j = 1;j <= n; j++)
        scanf("%d", &map[i][j]);
    for (i = 0; i <= n; i++) {
      cal[i][0] = 0;
      cal[0][i] = 0;
    }
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        cal[i][j] = cal[i - 1][j] + cal[i][j - 1] - cal[i - 1][j - 1] + map[i][j];
    int a, c, start, all, ans = 0;
    for (a = 1; a <= n; a++)
      for (c = a; c <= n; c++) {
        start = cal[c][n] - cal[a - 1][n] - cal[c][n - 1] + cal[a - 1][n - 1];
        all = start;
        for (i = n - 1; i >= 1; i--) {
          if (start < 0) start = 0;
          start += (cal[c][i] - cal[a - 1][i] - cal[c][i - 1] + cal[a - 1][i - 1]);
          if (start > all) all = start;
        }
        if (all > ans) ans = all;
      }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言