首页 文章

寻找最大子阵列的分而治之算法 - 如何提供结果子阵列索引？

提问于
浏览 次
4

对不起，我有一个使用Brute Force Algorithm O(n^2)，Divide and Conquer O(nlogn)和Kadane's Algorithm O(n)解决Maximum Sub Array Problem的任务 . （我的代码不同） .

“例如，对于值{-2,1，-3,4，-1,2,1，-5,4}的序列，具有最大总和的连续子数组是[4，-1， [1]，总和6.“ - 来自Wiki页面 .

我完成了Kadane和BruteForce，其中我所需的输出不仅仅是找到总和，还有找到的子数组的 starting index 和 ending index .

我当前的 DivideAndConquer 代码给了我正确的总和 . 但是，我可以't see a way to keep track of my indexes since I implemented it recursively (of course). And I don'知道在这种情况下唯一的方法是使用全局变量（我不喜欢）..你能帮忙解决这个问题吗？或者我需要改变整个设计吗？

#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;
}
c++ algorithm recursion logic divide-and-conquer

1 回答

  • 4

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

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

    • 包含左元素的最大总和（s_l）

    • 包含正确元素的最大总和（s_r）

    • 整个数组的总和（t）

    • 以上值的最大值（mx）

    对于检查大小为1的子数组的情况，所有这些值都等于该元素的值 . 合并两个子数组（sub_left，sub_right）时，这些值将为：

    • s_l = max（sub_left.s_l，sub_left.t sub_right.s_l）

    • s_r = max（sub_right.s_r，sub_right.t sub_left.s_r）

    • t = sum（sub_left.t sub_right.t）

    • 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;
}

    NOTE: 此算法在 O(n) 时间运行 .

    回复于

相关问题