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 kimmyer kimmayer

댓글을 달아 주세요


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

공지사항

Yesterday4
Today1
Total6,419

달력

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

최근에 달린 댓글

최근에 받은 트랙백

글 보관함