분할 정복 (1)

[코드]

#include <stdio.h>

typedef struct
{
	int left_idx;
	int right_idx;
	int max;
}sub;

int array[1000];

sub MaxCrossingSubArray(int left, int right)
//left와 right를 크로스하는 Maximum SubArray를 구하는 함수
{
	int mid = (left + right) / 2;
	int i;
	int max_left = -1000;
	int left_idx;
	int max_right = -1000;
	int right_idx;
	int sum_left = 0;
	int sum_right = 0;
	sub x;

	for (i = mid; i >= left; i--)
	{
		sum_left += array[i];
		if (sum_left > max_left)
		{
			max_left = sum_left;
			left_idx = i;
		}
	}

	for (i = mid + 1; i <= right; i++)
	{
		sum_right += array[i];
		if (sum_right > max_right)
		{
			max_right = sum_right;
			right_idx = i;
		}
	}

	x.left_idx = left_idx;
	x.right_idx = right_idx;
	x.max = max_left + max_right;

	return x;
}

sub MaximumSubArray(int left, int right)
{
	sub x, y, z;
	if (left == right)
	{
		x.left_idx = left;
		x.right_idx = right;
		x.max = array[left];

		return x;
	}

	int mid = (left + right) / 2;

	x = MaximumSubArray(left, mid);
	y = MaximumSubArray(mid + 1, right);
	z = MaxCrossingSubArray(left, right);
    //각각 왼쪽, 오른쪽, 크로스 Maximum SubArray

	if (x.max < y.max)
	{
		if (y.max < z.max) return z;
		else return y;
	}

	else
	{
		if (x.max < z.max) return z;
		else return x;
	}
}

int main()
{
	int T;
	int i, j, N;

	sub x;
	scanf("%d", &T);

	for (i = 0; i < T; i++)
	{
		scanf("%d", &N);

		for (j = 0; j < N; j++)
		{
			scanf("%d", &array[j]);
		}

		x = MaximumSubArray(0, N - 1);

		printf("%d %d %d\n", x.max, x.left_idx, x.right_idx);
	}
	
	return 0;
}

분할 정복의 분석

//이는 뒤의 DP에서 한번 더 연습해볼 것이다.