최대합 부분배열

문제 : 길이가 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 가 된다.

 

이 문제에 대해 여러가지 방법이 있는데 가장 쉬운 방법부터 소개하겠다.

 

1. 부분합 수열 : O(n^2)

 

int MaxLoof(int *arr, int n)
{
    int i,j,tmp,res;
 
    res=0;
 
    for(i=0;i<=n;i++)
    {
        tmp=0;
        for(j=i;j<=n;j++)
        {
            tmp+=arr[j];
            if(tmp>res)
                res=tmp;
        }
    }
    return res;
}

 

무식하게 푸는 방법으로 배열의 모든 경우의 합을 구하는 것이다.

하지만 이 방법은 Divide-and-Conquer 전략을 이용하지도 않는다.

 

좀 더 빠르고 효율적으로 계산하기 위한 방법은 분할 정복이 있다.

 

2. 분할정복 : O(nlogn)

#include <stdio.h>
 
int Maximum(int *arr, int a, int b)
{
    if(a==b)
        return arr[a];  
    int mid=(a+b)/2;
    int left=Maximum(arr,a,mid);
    int right=Maximum(arr,mid+1,b);
 
    int i,tmp,left_part,right_part;
 
    tmp=0;
    left_part=-999999;
 
    for(i=mid;i>=a;i--)
    {    
        tmp+=arr[i];
        left_part=Max(left_part, tmp);
    }
 
    tmp=0;
    right_part=-999999;
    for(i=mid+1;i<=b;i++)
    {
        tmp+=arr[i];
        right_part=Max(right_part,tmp);
    }
    return Max2(left,right,left_part+right_part);
}