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;
}