<C언어 알고리즘> 최대합 부분배열

길이가 n인 정수의 배열 A[0..n-1]가 있다. A[a] + A[a+1] + … + A[b]의 값을 최대화하는 구간 (a,b)를 찾는 방법을 Divide-and-Conquer 전략을 이용하여 설계하고 분석하라.
예를 들어, 배열 A가 아래와 같이 주어졌을 경우
(n=10), {31,-41,59,26,-53,58,97,-93,-23 ,84}
답은 a=2, b=6 인 경우의 59+26-53+58+97=187이 된다.

---

Solution

O(n^3)의 풀이

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int maximum_partial_array(int *arr,int size)
{
	int max_value=arr[0], max_a=0, max_b=0;

	for(int i=0;i<size;i++)
		for(int j=i;j<size;j++)
		{
			int sum=0;

			for(int k=i;k<=j;k++)
				sum+=arr[k];

			max_a=max_value>sum?max_a:i;
			max_b=max_value>sum?max_b:j;
			max_value=max_value>sum?max_value:sum;
		}

	printf("maximum sum: %d\n",max_value);
	return 100*max_a+max_b;
}

int main(void)
{
	int size, *arr=NULL, ab;
	srand((unsigned)time(NULL));

	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	printf("initial array: ");
	for(int i=0;i<size;i++)
	{
		arr[i]=rand()%200-100;
		printf("%d ", arr[i]);
	}
	printf("\n");

	ab=maximum_partial_array(arr,size);
	printf("a:%d, b:%d\n", ab/100, ab%100);

	free(arr);
	return 0;
}

 

O(n^2)의 풀이

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int maximum_partial_array(int *arr,int size)
{
	int max_value=arr[0], max_a=0, max_b=0;

	for(int i=0;i<size;i++)
	{
		int sum=0;

		for(int j=i;j<size;j++)
		{
			sum+=arr[j];

			max_a=max_value>sum?max_a:i;
			max_b=max_value>sum?max_b:j;
			max_value=max_value>sum?max_value:sum;
		}
	}

	printf("maximum sum: %d\n",max_value);
	return 100*max_a+max_b;
}

int main(void)
{
	int size, *arr=NULL, ab;
	srand((unsigned)time(NULL));

	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	printf("initial array: ");
	for(int i=0;i<size;i++)
	{
		arr[i]=rand()%200-100;
		printf("%d ", arr[i]);
	}
	printf("\n");

	ab=maximum_partial_array(arr,size);
	printf("a:%d, b:%d\n", ab/100, ab%100);

	free(arr);
	return 0;
}

 

O(nlogn)의 풀이: Divide-and-Conquer 전략

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

long long int maximum_partial_array(int *arr,int low,int high)
{
	int mid=(low+high)/2, left_a, left_b, right_a, right_b, left_part_a=(low+high)/2+1, right_part_b=(low+high)/2, sum=0;
	long long int left, right, left_part_value=-999999, right_part_value=-999999;

	if(low==high)
		return 10000*arr[low]+101*low;

	left=maximum_partial_array(arr,low,mid);
	right=maximum_partial_array(arr,mid+1,high);
	left_a=(left/100)%100;
	left_b=left%100;
	right_a=(right/100)%100;
	right_b=right%100;

	for(int i=mid;i>=low;i--)
	{
		sum+=arr[i];
		left_part_a=left_part_value>sum?left_part_a:i;
		left_part_value=left_part_value>sum?left_part_value:sum;
	}

	sum=0;
	for(int i=mid+1;i<=high;i++)
	{
		sum+=arr[i];
		right_part_b=right_part_value>sum?right_part_b:i;
		right_part_value=right_part_value>sum?right_part_value:sum;
	}

	if(left/10000>=right/10000 && left/10000>=left_part_value+right_part_value)
		return left;
	else if(left_part_value+right_part_value>=left/10000 && left_part_value+right_part_value>=right/10000)
		return 10000*(left_part_value+right_part_value)+100*left_part_a+right_part_b;
	else
		return right;
}

int main(void)
{
	int size, *arr=NULL;
	long long int result;
	srand((unsigned)time(NULL));

	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	printf("initial array: ");
	for(int i=0;i<size;i++)
	{
		arr[i]=rand()%200-100;
		printf("%d ", arr[i]);
	}
	printf("\n");

	result=maximum_partial_array(arr,0,size-1);
	printf("a:%lld, b:%lld, sum:%lld\n", (result/100)%100, result%100, result/10000);

	free(arr);
	return 0;
}

 

O(n)의 풀이

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int maximum_partial_array(int *arr,int size)
{
	int max_value=arr[0], max_a=0, max_b=0, sum=0, sum_a=0, sum_b=0;

	for(int i=0;i<size;i++)
	{
		sum_a=arr[i]+sum>arr[i]?sum_a:i;
		sum_b=i;
		sum=arr[i]+sum>arr[i]?arr[i]+sum:arr[i];

		max_a=max_value>=sum?max_a:sum_a;
		max_b=max_value>=sum?max_b:sum_b;
		max_value=max_value>=sum?max_value:sum;
	}

	printf("maximum sum: %d\n",max_value);
	return 100*max_a+max_b;
}

int main(void)
{
	int size, *arr=NULL, ab;
	srand((unsigned)time(NULL));

	scanf("%d", &size);
	arr=(int *)malloc(size*sizeof(int));

	printf("initial array: ");
	for(int i=0;i<size;i++)
	{
		arr[i]=rand()%200-100;
		printf("%d ", arr[i]);
	}
	printf("\n");

	ab=maximum_partial_array(arr,size);
	printf("a:%d, b:%d\n", ab/100, ab%100);

	free(arr);
	return 0;
}