2015. 2. 10. 18:18 Programing/Algorithm
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 |