9

免责声明：这是一个任务。我不要求明确的代码，只需要足够的帮助来理解所涉及的算法，以便我可以修复代码中的错误。

好的，所以您可能熟悉最大子数组问题：计算并返回数组中最大的连续整数块。很简单，但这个任务需要我以三种不同的复杂度来完成：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;
}
4

4 回答 4

5

我仍然盯着你的问题，但我几乎立即注意到了几个错误。

首先，如果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 允许你这样做，你应该利用它。我想你会发现它使数字更容易理解，并且不需要你传入的索引之一。

例如：一个接受数组、中间分割和递归的函数可能看起来像这样：

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 开始的数组。不知道你是否可以使用它，但它确实让它更容易掌握（至少对我来说）。

最后，我可以看到，您的除法似乎没有做太多递归，这将是一个问题，因为这毕竟是一种递归算法。看来你至少错过了一个电话divide()。

我可能错过了一些东西，这不是第一次，但正如我所说，我没有倾注太多（还）。

于 2013-02-01T03:53:33.217 回答
3

John Bentley 于 1984 年就此发表了一篇论文。您可以在线免费找到 PDF：http ://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/05/Bentley84.pdf

他在第二页开始讨论 O(n log n) 方法。

于 2013-02-01T02:20:19.587 回答
2

我认为您几乎拥有所需的所有代码，但是这两个问题对我来说很突出：

  • mid变量计算是可疑的。
  • 你的divide功能并没有真正做任何划分。

在分治的递归公式中，您将在数组的下半部分递归调用您的除法函数，然后在数组的上半部分调用。征服步骤可以被认为是计算重叠和并返回三个候选者中最大者的代码。

编辑：当递归地思考问题时，实现函数的目的，并利用它。在这种情况下，该divide函数将返回所提供数组的最大子数组总和。因此，计算的方法maxLeftSum是在左子数组上调用除法。同样对于maxRightSum。

int divide(int arr[], int start, int end) {
    if (end > start) {
        int mid = (start + end)/2;
        int maxLeftSum = divide(arr, start, mid);
        int maxRightSum = divide(arr, mid+1, end);
        return conquer(arr, start, end, maxLeftSum, maxRightSum);
    }
    return (start == end) ? arr[start] : 0;
}

祝你好运！

于 2013-02-01T03:47:39.213 回答
1

我认为您只关注交叉子阵部分。但是，也有左子阵部分和右子阵部分，它们都有比交叉子阵更大的可能性。

因为英语不是我的第一语言而且我不擅长它。我不相信我已经表达了我想要表达的确切内容，所以我将粘贴我的代码。这是我的代码：

int find_max_subarr(int a[],int l,int r)
{
    if(l>r)return 0;
    if(l==r) return a[l];
    int lsum=-1000,rsum=-1000;
    int sum=0;
    if(l<r) {
        int mid=(l+r)/2;
        for(int i=mid;i>=l;i--) {
            sum+=a[i];
            if(lsum<sum)lsum=sum;
        }
        sum=0;
        for(int i=mid+1;i<=r;i++) {
            sum+=a[i];
            if(rsum<sum)rsum=sum;
        }
        int all_sum=lsum+rsum;
        int llsum=find_max_subarr(a,l,mid);
        int rrsum=find_max_subarr(a,mid+1,r);
        if(llsum<all_sum&&rrsum<all_sum) return all_sum;
        if(all_sum<llsum&&rrsum<llsum)return llsum;
        if(all_sum<rrsum&&llsum<rrsum)return rrsum;
    }
}

int main()
{
    int a[SUM]={100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
    int b[SUM-1];
    int t=0;
    for(int i=1;i<SUM;i++) {
        b[t]=a[i]-a[i-1];
        t++;
    }
    int sum=find_max_subarr(b,0,t-1);
    cout<<sum<<endl;
    return 0;
}
于 2013-06-04T11:19:47.350 回答