'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
Kadane's Algorithm  (0) 2015.02.10
Posted by thread1525

댓글을 달아 주세요

이전버튼 1 이전버튼

블로그 이미지
1525번 thread 입니다.
thread1525

공지사항

Yesterday4
Today0
Total6,281

달력

 « |  » 2019.11
          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

최근에 달린 댓글

최근에 받은 트랙백

글 보관함