[C++] Maximum Sum (upgrade)

2004.05.18 00:57IT/소스코드

[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;
}
  • 프로필사진
    zzun2004.05.19 03:19 신고

    우선 1차원 행렬에서 maxsum substring을 O(N)에 구하는 알고리즘

    a1, a2, ..., ax, ..., ay, ay+1, ..., ak-1, ak, ...
    이런 행렬이 있다고 치고,
    a1~ak-1 중에 maxsum substring을 ax...ay 라고 하자.

    그렇다면 위의 조건을 이용하여 a1~ak의 maxsum substring을 O(1) 안에 구할 수 있으면
    귀납법으로 전체의 maxsum substring을 O(N) 안에 구할 수 있게된다.

    a1~ak의 maxsum substring이 될 수 있는 후보는,
    1. a1~ak-1의 최대값인 ax...ay : max
    2. 새로운 원소 하나 ak
    3. 또 다른 스트링 az...ak (단, x<=z<k) : candi
    위에서 1번과 3번을 편의상 max랑 candi라고 부르자.

    여기서 candi 값을 잘 유지하는게 중요한데
    임의의 점부터 현재원소까지의 합 중 maximum 값을 유지해야 한다.
    (즉, ak를 끝점으로 하는 substring 중에 max를 말한다.)

    위의 과정을 하는 코드를 짜보면..


    max = -inf; candi=0;
    for k=1 to k=N
    {
    candi += ak
    if ( ak > max && ak > candi )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max = candi = ak; // 위에서 2번 후보에 해당
    else if ( candi > max )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max = candi;&nbsp;&nbsp;// 위에서 3번 후보에 해당
    else if ( ak > candi )
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;candi = ak; // candi를 최신으로 유지하기 위한 코드
    } // 위에서 1번 후보의 경우는 max값을 갱신할 필요 없음
    print max;



    이래서 1차원 행렬의 max를 O(N) 만에 구할 수 있다.

    이것을 2차원에 적용하는 방법은
    사각형의 네 좌표를 [,]-[,] 식으로 나타낸다면
    [0,a]-[0,b] (a,b는 임의의 수) 같은 사각형은 총 O(N^2)개 존재한다.
    이 각 사각형들 내부의 합은 우리가 N^4할때 썼던 방법으로 쉽게 구하고
    이 사각형 중 maximum은 위에서 언급한 1차원 알고리즘으로 구할 수 있다.
    즉, O(N) 시간안에 최대값을 구할 수 있다는 얘기다.
    이런 방법으로 [0,a]-[1,b] 의 최대값, [2,a]-[5,b] 의 최대값
    식으로 구하면
    총 O(N^2)개의 최대값을 O(N^3) 시간 안에 구할 수 있고
    그 모든 최대값 중에 최대값이 바로 우리가 원하는 값이다.

  • 프로필사진
    2004.05.22 19:22 신고

    좀 퍼갈께..ㅋㅋ

1 2 3 4 5 6 7 8 9 ··· 24