最大子阵列:分而治之

Question

免责声明:这是一项任务.我不是要求显式代码,只是有足够的帮助来理解所涉及的算法,以便我可以修复代码中的错误.

好的,所以你可能熟悉最大的子阵列问题:计算并返回数组中最大的连续整数块.很简单,但这个任务需要我以三种不同的复杂性来做:O(n ^ 3),O(n ^ 2)和O(n log n).我已经得到了前两个没有太多麻烦(蛮力),但第三个让我头疼......字面意思.

我理解该算法应该如何工作:一个数组被传递给一个函数,该函数递归地将它分成两半,然后比较各个组件以找到每一半中的最大子数组.然后,因为最大子阵列必须完全位于左半部分或右半部分,或者在与两者重叠的部分中,所以必须找到与左右重叠的最大子阵列.比较每种情况的最大子阵列,最大值将是您的返回值.

我相信我已经编写了充分执行该任务的代码,但在评估中我似乎错了.我一直在努力联系教练和助教,但是我觉得我不能随便找到他们中的任何一个.下面是我到目前为止编写的代码.如果你发现任何明显错误,请告诉我.同样,我不是在寻找明确的代码或答案,而是帮助理解我做错了什么.我已经查看了这里提供的所有类似案例,但没有找到任何可以帮助我的东西.我也做了大量的谷歌搜索指导,但这也没有多大帮助.无论如何,这是有问题的代码:

int conquer(int arr[], int first, int mid, int last) {

    int i = 0;
    int maxLeft = 0;
    int maxRight = 0;

    int temp = 0;
    for (i = mid; i >= first; i--) {
        temp = temp + arr[i];
        if (maxLeft < temp) {
            maxLeft = temp;
        }
    }
    temp = 0;
    for (i = (mid + 1); i <= last; i++) {
        temp = temp + arr[i];
        if (maxRight < temp) {
            maxRight = temp;
        }
    }

    return (maxLeft + maxRight);
}

int divide(int arr[], int start, int end) {

    int i;
    int maxSum;
    int maxLeftSum;
    int maxRightSum;
    int maxOverlapSum;

    if (start == end) {
        return arr[start];
    } else {
        int first = start;
        int mid = (end / 2);
        int last = end;

        maxSum = 0;
        maxLeftSum = 0;

        for (i = first; i < mid; i++) {
            maxSum = maxSum + arr[i];
            if (maxLeftSum < maxSum) {
                maxLeftSum = maxSum;
            }
        }
        for (i = (mid + 1); i < last; i++) {
            maxSum = maxSum + arr[i];
            if (maxRightSum < maxSum) {
                maxRightSum = maxSum;
            }
        }

        maxOverlapSum = conquer(arr, first, mid, last);
    }

    if ((maxLeftSum > maxRightSum) && (maxLeftSum > maxOverlapSum)) {
        return maxLeftSum;
    } else if ((maxRightSum > maxLeftSum) && (maxRightSum > maxOverlapSum)) {
        return maxRightSum;
    } else
        return maxOverlapSum;
}

编辑:我得到的错误是不正确的结果.我的两个算法之间的结果一致且正确,但这个算法不正确.

编辑#2:这是我的代码的更新版本,稍微减少了一些,我修复了一些问题.它仍然没有正常运行,但它应该更接近......

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

int numarr[] = {22, -27, 38, -34, 49, 40, 13, -44, -13, 28, 46, 7, -26, 42,
        29, 0, -6, 35, 23, -37, 10, 12, -2, 18, -12, -49, -10, 37, -5, 17,
        6, -11, -22, -17, -50, -40, 44, 14, -41, 19, -15, 45, -23, 48, -1,
        -39, -46, 15, 3, -32, -29, -48, -19, 27, -33, -8, 11, 21, -43, 24,
        5, 34, -36, -9, 16, -31, -7, -24, -47, -14, -16, -18, 39, -30, 33,
        -45, -38, 41, -3, 4, -25, 20, -35, 32, 26, 47, 2, -4, 8, 9, 31, -28,
        36, 1, -21, 30, 43, 25, -20, -42};

int length = ((sizeof(numarr))/(sizeof(int)));

int divide(int left, int right) {

    int mid, i, temp, mLeft, mRight, mCross = 0;

    if (left == right) {
        return left;
    } else if (left > right) {
        return 0;
    } else {
        mid = (left + right) / 2;

        divide(left, mid);
        divide(mid + 1, right);

        for (i = mid; i >= left; i--) {
            temp = temp + numarr[i];
            if (mLeft < temp) {
                mLeft = temp;
            }
        }

        for (i = mid + 1; i <= right; i++) {
            temp = temp + numarr[i];
            if (mRight < temp) {
                mRight = temp;
            }
        }

        mCross = (mLeft + mRight);

        printf("mLeft:  %d\n", mLeft);
        printf("mRight: %d\n", mRight);
        printf("mCross: %d\n", mCross);

        return 0;
    }
}

int main(int argc, char const *argv[])
{
    divide(0, length);
    return 0;
}

Answer 1

我仍在盯着你的问题,但我几乎立即注意到了几个错误.

首先,如果first和last他们的名字有任何意图,你会发现中点不正确.你做这个:

mid = end/2;

什么时候应该这样:

mid = first + (last-first)/2;

接下来,您的第一个枚举循环从[first,mid) (请注意mid右侧的排除)开始.这个循环就不会包含arr[mid]元素:

    for (i = first; i < mid; i++) {

你的第二次运行[mid+1,last),也不包括arr[mid]元素:

    for (i = (mid + 1); i < last; i++) {

这留下了一个元素的漏洞,特别是arr[mid].现在,我并没有声称我完全理解算法,因为我几乎没有机会阅读它,但如果你的目的是覆盖整个范围[first,last),那么这可能不会这样做.此外,由SauceMaster链接的论文所提出的教科书算法的明显缺点是使用一种语言,它不允许你偏移到数组中,并通过指针衰减将其作为一个函数调用传递给一个函数调用.阵列.C允许你这样做,你应该利用它.我认为你会发现它使数字更容易理解,并且不再需要你传入的索引.

例如:一个接受数组和mid-splits和recurses的函数可能看起来像这样:

void midsplit( int arr[], int len)
{
    if (len < 2)
    {
         // base case
    }
    else
    {
        int mid = len/2;
        midsplit(arr, mid);
        midsplit(arr+mid, len-mid);

        // cumulative case
    } 
}

在每次递归中,分割点始终是一个范围的结束,并用于偏移地寻址第二个范围,在递归调用中将其视为自己的基于0的数组.Dunno,如果你可以使用它,但它确实让它更容易(至少对我来说)掌握.

最后,你的鸿沟似乎没有做太多的递归,我可以看到,这将是一个问题,因为这毕竟是一个递归算法.看来你至少缺少一次电话divide().

我可能错过了一些东西,这不是第一次,但正如我所说的,我并没有过多地倾注它(还).