'Kadane's Algorithm'에 해당되는 글 1건

  1. 2015.02.10 Kadane's Algorithm

n^3 알고리즘으로서 주어지는 행렬의 sub array들로 만들어지는 직사각형들 중 최대 합을 가지고 있는 직사각형을 구하는 알고리즘,

 

 

void main(){

 char c;

 string s;

 int n;

 int row, col;

 ifstream fin;

 fin.open("testcase100.txt");

 getline(fin, s);

 istringstream input(s);

 input >> row;

 col = row;

 n = row;

 int **pt = new int *[row];

 for(int i = 0; i < row; i++)

  pt[i] = new int[col];

 

 int *c_pt = new int [row];

 /*for(int i = 0; i < row; i++)

  c_pt[i] = new int[col];*/

 

 int temp = 0;

 

 for(int i=0; i < row; i++)

  for(int j = 0; j < col; j++)

  {

   fin >> temp;

   pt[i][j] = temp;

  }

  

     

  int sum = 0;

  int sum_2 = 0;

  int max_sum = 0; 

  

  

 

 int t = 0;

   int S = 1<<31, d = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;

 

 

 for( int z = 0; z < n; z++)

    {

  for(int i = 0; i < n; i++) c_pt[i] = 0;

 

        for(int x = z; x < n; x++)

        {

            t = 0;

   d = 1<<31;

            j = 0;

            k = 0; l = 0;

   for(int i = 0; i < n; i++)

            {

    c_pt[i] = c_pt[i] + pt[x][i];

    t = t + c_pt[i];

    if( t > d)

                {

     d = t;

                    k = i;

                    l = j;

                }

                if( t < 0 )

                {

                    t = 0;

                    j = i + 1;

                }

            }

   if( d > S)

            {

    S = d;

                x1 = x;

                y1 = k;

                x2 = z;

                y2 = l;

            }

        }

    }

 

    cout << x1 << " " << y1 << " " << x2 << " "  << y2 << endl;

    cout << S;

 

    

}

'Programing > Algorithm' 카테고리의 다른 글

프로젝트 오일러 6번  (0) 2015.02.10
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 4번  (0) 2015.02.10
프로젝트 오일러 3번  (0) 2015.02.10
프로젝트 오일러 2번  (0) 2015.02.10
Posted by kimmayer
이전버튼 1 이전버튼

블로그 이미지
IT 기술들 정리, 독후감을 주로 남깁니다!
kimmayer

공지사항

Yesterday
Today
Total

달력

 « |  » 2024.3
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함