[C++] Maximum Sum

2004.05.10 04:09IT/소스코드

[info]
http://acm.uva.es/p/v1/108.html
내림피아드 프로젝트의 첫번째 문제
O(N^4) 알고리즘

[test.in]
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

[n01_zzun.cpp]
/**

Max-Sum Subrectangle Search

zzun
http://zzun.net
hello82@unitel.co.kr

**/

#include
#include
#include
#include

int array_size;
char** num_array;

bool read_input(char* filename)
{
       ifstream fin;
       int buf;

       fin.open( filename );

       fin >> array_size;        // take the array size N
       if ( array_size <=>               return false;
       }

       num_array = new char*[array_size];
       for (int i=0; i<array_size; i++)
               num_array[i] = new char[array_size];        // 2-dim array M-allocate

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
               {
                       fin >> buf;
                       num_array[i][j] = (char) buf;        // take the values
               }
       
       fin.close();

       return true;
}

int main()
{
       char* input_filename;
       int** sum;
       int max = 1 << 31;
       int temp;

       input_filename = "test.in";        

       if ( !read_input(input_filename) )
               return -1;

       sum = new int*[array_size+1];        // 2-dim array for SUM from [0,0] to [x,y]
       for (int i=0; i<array_size+1; i++)
       {
               sum[i] = new int[array_size+1];
               sum[i]++;        // move the pointer to use the -1 index
       }
       sum++;        // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]

       for (int i=-1; i<array_size; i++)
       {
               sum[i][-1] = 0;
               sum[-1][i] = 0;        // init
       }

       for (int i=0; i<array_size*2-1; i++)
               for (int j=0; j<=i; j++)
                       if ( i-j < array_size && j < array_size )
                               sum[j][i-j] = num_array[j][i-j] + sum[j-1][i-j] + sum[j][i-j-1] - sum[j-1][i-j-1];        // calculate sum[][], O(N^2)

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
                       for (int k=0; k<=i; k++)
                               for (int l=0; l<=j; l++)
                               {
                                       temp = sum[i][j] - sum[i][l-1] - sum[k-1][j] + sum[k-1][l-1];        // calculate sum of subrectangle, O(N^4)
                                       if ( temp > max )
                                               max = temp;
                               }

       cout << max << endl;

       sum--;
       for (int i=0; i<array_size+1; i++)
       {
               sum[i]--;
               delete [] sum[i];
       }
       delete [] sum;        // M de-alloc

       return 0;
}
1 2 3 4 5 6 7 8 9 10 ··· 24