codeground 최대 직사각형

Codeground 최대 직사각형 https://www.codeground.org/practice/practiceProblemView

2차원 배열이 주어질 때 부분배열의 원소들의 합이 가장 큰 것을 구하는 문제이다.

사실 $O(N^4)$ 방법 밖에 생각이 나지 않아 풀어서 AC를 받았으나 $O(N^3)$풀이가 존재한다.

행의 구간합을 구해놓고 greedy하게 풀어나가는 해법이다.

#include <cstdio> #define max(a,b) ((a)>(b)?(a):(b)) int main(){     setbuf(stdout, NULL);     int T;     scanf("%d", &T);          for (int t = 1; t <= T; t++){         int N;         int sum[101][101] = { 0 };         scanf("%d", &N);         for (int n = 1; n <= N; n++)             for (int m = 1; m <= N; m++){                 scanf("%d", &sum[n][m]);                 sum[n][m] += sum[n][m - 1];    //행의 구간합 구함             }         int ans = -999999999;         for (int n = 1; n <= N; n++){             for (int m = n; m <= N; m++){                 int s = 0;                 for (int k = 1; k <= N; k++){                     int plus;                     plus = sum[k][m] - sum[k][n - 1];    //n은 m,k가 반복될때 고정되있음                     s = max(s + plus, plus);        //행을 이어붙일 경우, 이어붙이지 않을 경우                     ans = max(ans, s);                 }             }         }         printf("Case #%d\n", t);         printf("%d\n", ans);     }     return 0; } Colored by Color Scripter

cs