打扰一下，我有一个任务要解决 Maximum Sub Array Problem使用 Brute Force Algorithm O(n^2) , Divide and Conquer O(nlogn)和 Kadane's Algorithm O(n) . (我的代码不同)。

"For example, for the sequence of values {−2, 1, −3, 4, −1, 2, 1, −5, 4}, the contiguous sub-array with the largest sum is [4, −1, 2, 1] with sum 6." - From the Wiki Page.

我已经完成了 Kadane 和 BruteForce，我需要的输出不仅仅是找到总和，还有找到的子数组的起始索引和结束索引.

我当前的 DivideAndConquer 代码得到了正确的总和。但是，我看不到一种方法来跟踪我的索引，因为我递归地实现了它(当然)。而且我不知道在这种情况下是否唯一的方法是使用全局变量(我不喜欢)。你能帮忙解决这个问题吗？还是我需要更改整个设计？

#include <iostream>

int DivideAndConquer(int[], int);

int main()
{
    // Example 1
    //const int MyArraySize = 16;
    //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -> 10, sum = 43

    // Example 2
    const int MyArraySize = 8;
    int MyArray[MyArraySize] = { -2, -5, 6, -2, -3, 1, 5, -6 }; // answer: Index 2 -> 6, sum = 7

    int FinalResult;

    FinalResult = DivideAndConquer(MyArray, MyArraySize);
    std::cout << "Using Divide And Conquer: With O(nlogn) Sum = " << FinalResult << "\n\n";

    system("pause");
    return 0;
}

int DivideAndConquer(int* _myArray, int _myArraySize)
{
    if (_myArraySize == 1)
        return _myArray[0];

    int middle = _myArraySize / 2;
    int Result_LeftPortion = DivideAndConquer(_myArray, middle);
    int Result_RightPortion = DivideAndConquer(_myArray + middle, _myArraySize - middle);

    int LeftSum = -9999;
    int RightSum = -9999;
    int TotalSum = 0;

    for (int i = middle; i < _myArraySize; i++)
    {
        TotalSum += _myArray[i];
        RightSum = TotalSum < RightSum ? RightSum : TotalSum;
    }

    TotalSum = 0;

    for (int i = middle - 1; i >= 0; i--)
    {
        TotalSum += _myArray[i];
        LeftSum = TotalSum < LeftSum ? LeftSum : TotalSum;
    }

    int PartialResult = LeftSum < RightSum ? RightSum : LeftSum;
    int Result= (PartialResult < LeftSum + RightSum ? LeftSum + RightSum : PartialResult);

    return Result;
}

最佳答案

您的算法存在逻辑问题，不是最优的。您甚至没有使用 Result_LeftPortion、Result_RightPortion 值。您的最终结果始终是整个数组的 RightSum、LeftSum 和 TotalSum 中的最大值。来自所有其他子数组的值将被忽略。

用分治法解决这个问题的一种方法如下。您应该为每个子数组保存四个值:

1. 包含左元素的最大和 ( s_l )
2. 包含正确元素的最大和 ( s_r )
3. 整个数组的总和 ( t )
4. 上述值的最大值 ( mx )

如果您正在检查大小为 1 的子数组，所有这些值都等于该元素的值。 合并两个子数组(sub_left、sub_right)时，这些值将是:

1. s_l = max( sub_left.s_l, sub_left.t + sub_right.s_l )
2. s_r = max( sub_right.s_r, sub_right.t + sub_left.s_r )
3. t = sum( sub_left.t + sub_right.t )
4. mx = max( s_l, s_r, t, sub_right.mx, sub_left.mx, sub_left.r+sub_right.l)

最终结果将是数组的mx 的值。 为了找到具有最大总和的子数组的位置，您应该为每个值保留右索引和左索引，并在执行合并时相应地更新它们。考虑这种情况

sub_left.s_r range is (2,5)
sub_right.t range is (6,10)
if ( sub_right.t + sub_left.s_r > sub_right.s_r )
      s_r range = (2,10)

这是我的实现:

#include <iostream>
using namespace std;

struct node {
    //value, right index, left index
    int value,  r,  l;
    node(int _v, int _r, int _l){
        value = _v;
        r = _r;
        l = _l;
    }
    node (){}

};

struct sub {
    // max node containing left element
    // max node containing right element
    // total node
    // max node
    node s_l, s_r, t, mx;
    sub ( node _l, node _r, node _t, node _mx ){
        s_l = _l;
        s_r = _r;
        t = _t;
        mx = _mx;
    }
    sub(){}
};


sub DivideAndConquer(int* _myArray, int left, int right)
{

    if(right == left){
        node n (_myArray[left],right,left);
        return sub( n, n, n, n);
    }
    int mid = (left+right)/2;
    sub sub_left = DivideAndConquer( _myArray, left, mid);
    sub sub_right = DivideAndConquer( _myArray, mid+1, right);

    sub cur;
    if ( sub_left.t.value + sub_right.s_l.value > sub_left.s_l.value ){
        cur.s_l.value = sub_left.t.value + sub_right.s_l.value;
        cur.s_l.r = sub_right.s_l.r;
        cur.s_l.l = sub_left.s_l.l;
    } else {
        cur.s_l = sub_left.s_l;
    }

    if ( sub_right.t.value + sub_left.s_r.value > sub_right.s_r.value ){
        cur.s_r.value = sub_right.t.value + sub_left.s_r.value;
        cur.s_r.l = sub_left.s_r.l;
        cur.s_r.r = sub_right.s_r.r;
    } else {
        cur.s_r = sub_right.s_r;
    }

    cur.t.value = sub_right.t.value + sub_left.t.value;
    cur.t.r = sub_right.t.r;
    cur.t.l = sub_left.t.l;

    if ( cur.s_r.value >= cur.s_l.value &&
         cur.s_r.value >= cur.t.value &&  
         cur.s_r.value >= sub_left.mx.value &&
         cur.s_r.value >= sub_right.mx.value ){
        cur.mx = cur.s_r;
    } else if ( cur.s_l.value >= cur.s_r.value &&
         cur.s_l.value >= cur.t.value &&  
         cur.s_l.value >= sub_left.mx.value &&
         cur.s_l.value >= sub_right.mx.value ){
        cur.mx = cur.s_l;
    } else if ( sub_left.mx.value >= cur.s_l.value &&
         sub_left.mx.value >= cur.t.value &&  
         sub_left.mx.value >= cur.s_r.value &&
         sub_left.mx.value >= sub_right.mx.value ){
        cur.mx = sub_left.mx;
    } else {
        cur.mx = sub_right.mx;
    }

    if ( sub_left.s_r.value + sub_right.s_l.value > cur.mx.value ){
        cur.mx.value = sub_left.s_r.value + sub_right.s_l.value;
        cur.mx.l = sub_left.s_r.l;
        cur.mx.r = sub_right.s_l.r;
    }
    return cur;
}

int main()
{
    // Example 1
    //const int MyArraySize = 16;
    //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -> 10, sum = 43

    // Example 2
    const int MyArraySize = 8;
    int MyArray[MyArraySize] = { -2, -5, 6, -2, -3, 1, 5, -6 }; // answer: Index 2 -> 6, sum = 7

    sub FinalResult = DivideAndConquer(MyArray, 0,MyArraySize-1);
    std::cout << "Sum = " << FinalResult.mx.value << std::endl;
    std::cout << "( " << FinalResult.mx.l << " , " << FinalResult.mx.r << ")" << std::endl;

 //   system("pause");
    return 0;
}

注意:该算法的运行时间为O(n)。

关于c++ - 寻找最大子数组的分而治之算法 - 如何同时提供结果子数组索引？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39349745/