카다네 알고리즘

문제 : 정수로 이루어진 N x N 행렬이 있을때 사각형을 만들어 최대와 최소인 사각형을 만드는 알고리즘

출력 : 사각형의 좌측상단의 좌표, 우측하단의 좌표, 최댓값, 최솟값

/*Compiler : Visual Studio 2015 */
/*Language : C*/

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>

#pragma warning(disable:4996)//scanf 경고 해제
#define MAX 1000

double calc(double* arr, int* first, int* last, int arr_size);
void findroot(double *arr[], int SizeOfArray);

int main()
{
	int SizeOfArray;
	double **arr;
	scanf("%d\n", &SizeOfArray);//행과 열의 크기를 먼저 받음
	arr = (double**)malloc(sizeof(double *)*SizeOfArray);
	for (int i = 0; i < SizeOfArray; i++)
	{
		arr[i] = (double *)malloc(sizeof(double)*SizeOfArray);
	}//동적배열 생성

	for (int i = 0; i < SizeOfArray; i++)
	{
		for (int j = 0; j < SizeOfArray; j++)
		{
			scanf("%lf", &arr[i][j]);
		}
	}//동적으로 받은 array에 데이터를 대입

	findroot(arr, SizeOfArray);
	//대입이 끝난 arr을 findroot에 배열의 행과 열의 크기와 함께 대입
	
	for (int i = 0; i<SizeOfArray; i++) 
	{
		free(arr[i]);
	}

	free(arr);	//array 동적할당 해제
	getchar();	//실행 후 종료됨 방지
	return 0;
}


void findroot(double *arr[], int SizeOfArray)
{
	int R_Left, R_Right, R_Up, R_Down, left, right, i, first, last;
	const int size = SizeOfArray;
	double maxSum = LONG_MIN, minSum = LONG_MIN, PartSum[MAX], sum;
	printf("\n%d x %d MATRIX\n", SizeOfArray, SizeOfArray);//행렬 정보 출력

	//Finding Maxvalue
	for (left = 0; left < SizeOfArray; ++left)
	{
		memset(PartSum, 0, sizeof(PartSum));
		for (right = left; right < SizeOfArray; ++right)
		{
			//left부터 right까지의 부분합을 구함
			for (i = 0; i < SizeOfArray; ++i)
			{
				PartSum[i] = PartSum[i] + arr[i][right];
			}
			sum = calc(PartSum, &first, &last, SizeOfArray);
			//1차원에서의 최소를 구함
			if (sum > maxSum)
			{
				maxSum = sum;
				R_Left = left;
				R_Right = right;
				R_Up = first;
				R_Down = last;
			}
		}
	}

	printf("\n(%d, %d) (%d, %d)\n", R_Up + 1, R_Left + 1, R_Down + 1, R_Right + 1);
	//첫번째 요소를 1,1로 잡기 위해 1씩 더해서 출력해줌
	printf("MaxSum is: %lf\n", maxSum);
	//printing maxvalue

	//Findidng minvalue
	for (int i = 0; i < SizeOfArray; i++)
	{
		for (int k = 0; k < SizeOfArray; k++)
		{
			arr[i][k] = (-1)*arr[i][k];//음수는 양수로 양수는 음수로 바꿔준다.
		}
	}

	//위의 maxvalue를 찾는것과 같은 코드
	for (left = 0; left < SizeOfArray; ++left)
	{
		memset(PartSum, 0, sizeof(PartSum));
		for (right = left; right < SizeOfArray; ++right)
		{
			//left부터 right까지의 부분합을 구한다.
			for (i = 0; i < SizeOfArray; ++i)
			{
				PartSum[i] += arr[i][right];
			}
			sum = calc(PartSum, &first, &last, SizeOfArray);
			//1차원에서의 최대를 구한다.
			if (sum > minSum)
			{
				minSum = sum;
				R_Left = left;
				R_Right = right;
				R_Up = first;
				R_Down = last;
			}
		}
	}
	minSum = (-1)*minSum; // 양, 음수를 바꿔계산한 결과를 다시 바꿔준다.
	printf("\n(%d, %d) (%d, %d)\n", R_Up + 1, R_Left + 1, R_Down + 1, R_Right + 1);
	printf("MinSum is: %lf\n", minSum);
	//printing minvalue
}

//1차원에서의 maxvalue를 구한다.
double calc(double* arr, int* first, int* last, int arr_size)
{
	double sum = 0, maxSum = LONG_MIN;
	int start_index=0, p=0;
	*last = -1; // 음수일 경우를 검사한다.

	for (int i = 0; i < arr_size; ++i)
	{
		sum += arr[i];
		if (sum < 0)
		{
			sum = 0;
			start_index = i + 1;
		}
		else if (sum > maxSum)
		{
			maxSum = sum;
			*first = start_index;
			*last = i;
		}
	}
	//음수를 검사한다.
	if (*last != -1)
		return maxSum;
	
	//모두 음수일때
	maxSum = arr[0];
	*first = 0;
	*last = 0;

	//가장 큰 원소를 찾는다. 
	for (int i = 1; i < arr_size; i++)
	{
		if (arr[i] > maxSum)
		{
			maxSum = arr[i];
			*first = i;
			*last = i;
		}
	}
	//test 모두 양수일때 minvalue test
	for(int i = 0; i < arr_size; i++)
	{
		for (int j = 0; j < arr_size; j++)
		{
			if (arr[i] >= 0)
				p = 1;
		}
	}
	if (p == 0)
		maxSum = arr[0];
	//test exit
	return maxSum;
}

자세한 설명은 주석을 참조하면 될것같다..

질문은 댓글주세요!