[C++] Maximum Sum (upgrade)

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

[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 <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>

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 <= 0 )
       {
               cout << "Error : array size!" << endl;
               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 local_max, local_max_candi, 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 k=0; k<=i; k++)
               {
                       local_max = 1 << 31;
                       local_max_candi = 0;
                       for (int j=0; j<array_size; j++)
                       {
                               temp = sum[i][j] - sum[i][j-1] - sum[k-1][j] + sum[k-1][j-1];
                               local_max_candi += temp;
                               if ( temp > local_max && temp > local_max_candi )
                                       local_max = local_max_candi = temp;
                               else if ( local_max_candi > local_max )
                                       local_max = local_max_candi;
                               else if ( temp > local_max_candi )
                                       local_max_candi = temp;
                       }
                       max = (local_max > max) ? local_max : max;
               }

       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;
}