알고리즘 도론 연습 제4장 제1절: 최대 서브 그룹의 귀속 실현

먼저 사고방식을 말하자면 분치 사상을 이용하여 한 수조에 대해 세 가지 상황을 구분한다.[low,mid]、2.[mid, high]와 3.크로스오버 서브 그룹 [low,high]의 가장 큰 서브 그룹은 반드시 이 세 가지 상황 중의 하나에 나타난다.한편, 1, 2가지 상황은 최대자수조의 귀속 상황에도 똑같이 적용된다. 즉, 1, 2가지 상황의 귀속 사상과 한 수조의 최대자수조를 구하는 문제는 같다.그래서 우리는 최대 경계를 뛰어넘는 자수조만 구할 수 있다면 답을 찾을 수 있다.
크로스오버의 가장 큰 자수조를 구하는 사고방식은 [i,mid]와 [mid+1,i]의 상황을 보고 이 두 가지 상황의 최대치와 경계를 구하고 최대치를 화합하면 크로스오버의 가장 큰 자수조와 좌우의 경계치를 찾을 수 있다.다음은 크로스오버의 가장 큰 하위 그룹을 구하는 C 언어의 실현이다.

int *findMaxCrossingSubarray(int arr[], int low, int mid, int high)
{
    int *a = calloc(3, sizeof(int));
    int leftSum = INT_MIN;
    int leftMaxIndex = low;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += arr[i];
        if (sum > leftSum)
        {
            leftSum = sum;
            leftMaxIndex = i;
        }
    }
    int rightSum = INT_MIN;
    int rightMaxIndex = high;
    sum = 0;
    for (int i = mid + 1; i <= high; i++)
    {

        sum += arr[i];
        if (sum > rightSum)
        {
            rightSum = sum;
            rightMaxIndex = i;
        }
    }
    a[0] = leftMaxIndex;
    a[1] = rightMaxIndex;
    a[2] = leftSum + rightSum;
    return a;
}

쉽게 누락되는 곳: 순환할 때 i의 경계 조건.다음 코드는 완전한 C 언어 반복 구현입니다.

// 
#include 
#include 
#include 

int *findMaxCrossingSubarray(int arr[], int low, int mid, int high); // 
int *findMaximumSubarray(int arr[], int low, int high);              // 

int main()
{
    int arr[16] = {13, -3, -25, 1, -3, 16, 23, 18, -20, -7, -12, -50, -22, 15, -4, 7};
    int *result = findMaximumSubarray(arr, 0, 15);
    printf(" %d", result[0]);
    printf(" %d", result[1]);
    printf(" %d", result[2]);
    free(result);
    return 0;
}
// 
int *findMaxCrossingSubarray(int arr[], int low, int mid, int high)
{
    int *a = calloc(3, sizeof(int));
    int leftSum = INT_MIN;
    int leftMaxIndex = low;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += arr[i];
        if (sum > leftSum)
        {
            leftSum = sum;
            leftMaxIndex = i;
        }
    }
    int rightSum = INT_MIN;
    int rightMaxIndex = high;
    sum = 0;
    for (int i = mid + 1; i <= high; i++)
    {

        sum += arr[i];
        if (sum > rightSum)
        {
            rightSum = sum;
            rightMaxIndex = i;
        }
    }
    a[0] = leftMaxIndex;
    a[1] = rightMaxIndex;
    a[2] = leftSum + rightSum;
    return a;
}

int *findMaximumSubarray(int arr[], int low, int high)
{
    int *a = calloc(3, sizeof(int));
    if (high == low)
    {
        a[0] = low;
        a[1] = high;
        a[2] = arr[low];
        return a;
    }
    int mid = (low + high) / 2;
    int *leftResult = findMaximumSubarray(arr, low, mid);
    int *rightResult = findMaximumSubarray(arr, mid + 1, high);
    int *midResult = findMaxCrossingSubarray(arr, low, mid, high);
    if (leftResult[2] >= midResult[2] && leftResult[2] >= rightResult[2])
    {
        free(rightResult);
        free(midResult);
        return leftResult;
    }
    else if (rightResult[2] >= midResult[2] && rightResult[2] >= leftResult[2])
    {
        free(leftResult);
        free(midResult);
        return rightResult;
    }
    else
    {
        free(leftResult);
        free(rightResult);
        return midResult;
    }
}

복잡도는 O(nlgn)로 끝났습니다.