행렬의 최대 사각형의 합(max sum of rectangle)

네이버 답변에서 퍼온 소스 (익명으로 올린 소스)

약간의 문제점을 발견함, 소화필요.

(확장자는 .cpp 로 해야 돌아감, 그러니까 이 소스를 c언어에 넣을 수 있는 것인가? 약간은 의문이 됨)

#include <stdio.h> 

#include <stdlib.h> 

#include <time.h> 

#include <limits.h> 

#define N 25 

#define RANDNUM_RANGE 9 

int array[N+2][N+2] = {0,}, sum[N+2][N+2] = {0,}; 

void fillArrayWithRandNum(){ 

     srand( time(NULL) );  

     int dataIdx=0; 

     for(int row=1; row<=N; row++) 

         for(int col=1; col<=N; col++){ 

                array[row][col] = ((rand()%RANDNUM_RANGE)+1) * (rand()%2==0?-1:1); 

                printf("%2d%s",array[row][col],col==N?"\n":","); 

         }  

} 

int sumBetween(int leftCol, int rightCol, int row, int sum[N+2][N+2]){ 

     return sum[row][rightCol] - sum[row][leftCol-1]; 

} 

int main(){ 

     fillArrayWithRandNum(); 

      

     for(int row=1; row<=N; row++) 

        for(int col = 1; col <= N; col++) 

           sum[row][col] = sum[row][col-1] + array[row][col]; 

     int totalBestSum = INT_MIN; 

     int rectTop = 0, rectBottom = 0, rectLeft = 0, rectRight = 0; 

     for(int leftCol=1; leftCol<=N; leftCol++){ 

            for(int rightCol=leftCol; rightCol<=N; rightCol++){ 

                   int curSum = 0, curBestSum = INT_MIN; 

                   int curBottom = 0, curTop = 1; 

                   for(int row=1; row<=N; row++){ 

                          int rowSum = sumBetween(leftCol, rightCol, row, sum); 

                          curSum += rowSum; 

                          if(curSum > curBestSum){  

                                 curBestSum = curSum; 

                                 curBottom = row; 

                          } 

                          if(curSum < 0){ 

                                 curSum = 0;    

                                 curTop = row + 1; 

                          } 

                   } 

                   if (curBestSum > totalBestSum) { 

                          totalBestSum = curBestSum; 

                          rectLeft = leftCol; 

                          rectRight = rightCol; 

                          rectTop = curSum>0?curTop:curBottom; 

                          rectBottom = curBottom; 

                   } 

            } 

     } 

     if(rectTop>rectBottom) { int t=rectTop; rectTop=rectBottom; rectBottom=t; printf("#"); }

     printf("\n%d (%d,%d) (%d,%d)\n\n",totalBestSum, rectTop, rectLeft, rectBottom, rectRight); 

     int check=0;

     for(int row=rectTop; row<=rectBottom; row++) 

         for(int col=rectLeft; col<=rectRight; col++) {

             check+=array[row][col];

             printf("%2d%s",array[row][col],col==rectRight?"\n":",");

         }

     printf("\ncheck=%d", check); 

     return 0;

}