Алгоритм разделения и владения для поиска максимального подмассива - как также предоставить индексы подмассивов результатов?

Извините, у меня есть задание решить проблему максимального подмассива с помощью Алгоритм грубой силы O (n ^ 2), Разделяй и властвуй O (nlogn) и Алгоритм Кадана O (n). (У меня другой код).

«Например, для последовательности значений {−2, 1, −3, 4, −1, 2, 1, −5, 4} непрерывный подмассив с наибольшей суммой равен [4, −1, 2, 1] с суммой 6.» - со страницы Wiki.

Я закончил с Kadane's и 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;
}

c++ recursion logic algorithm divide-and-conquer
person Khalil Khalaf    schedule 06.09.2016    source источник
comment
Можете ли вы иметь другую выходную переменную (по ссылке) для вашей рекурсивной функции?   -  person πάντα ῥεῖ    schedule 06.09.2016
comment
@ πάνταῥεῖ Да. Что-то вроде return Tuple<int, int*, int*> или & вполне нормально. Но я все еще не понимаю, как мне отслеживать индексы, поскольку я не делаю это итеративно ...   -  person Khalil Khalaf    schedule 06.09.2016
comment
Вы получили этот ответ вчера (более или менее) :)   -  person πάντα ῥεῖ    schedule 06.09.2016
comment
@ πάνταῥεῖ Заводская вещь или предложенная return Tuple<..>?   -  person Khalil Khalaf    schedule 06.09.2016
comment
Я только что видел return Tuple<> (соответственно Pair). Поскольку вы вызываете рекурсивно, я думаю, что параметр по ссылке кажется более подходящим, чем возвращаемое значение.   -  person πάντα ῥεῖ    schedule 06.09.2016
comment
Что ж, это была идея обсуждения, но не ответ. И код начинается с середины входного массива и рекурсивно левая половина, затем правая половина .. Пока я не получу свое решение, в котором каждый узел (отдельный элемент) сравнивается со своим соседом, затем их результат сравнивается со сравнением их соседей результат и так далее ... Я не понимаю, как я могу отслеживать индексы и возвращать их с ответом. Вы можете показать мне, пожалуйста? @ πάνταῥεῖ   -  person Khalil Khalaf    schedule 06.09.2016
comment
Я сейчас на работе. Некогда сожалеть.   -  person πάντα ῥεῖ    schedule 06.09.2016
comment
Правда @ πάνταῥεῖ: P Что ты делаешь с моим постом, если у тебя нет времени? Это нормально, если вы не знаете ответ, который знаете: P   -  person Khalil Khalaf    schedule 06.09.2016
comment
Это неправильный код. проверьте -2, -5, 6, -2, -3, 1, -5, -6 , он возвращает 1.   -  person Saeid    schedule 06.09.2016
comment
@ sudomakeinstall2 См. отредактировано. У меня была опечатка. Мне очень жаль, но последнее слово в самой последней строке должно быть PartialResult, а не Result. Ваш пример дает мне 4, что является правильным [6, -2] индексом 2 to 3 (если я тестирую с использованием других алгоритмов). Я сейчас дома и работаю над этим   -  person Khalil Khalaf    schedule 06.09.2016
comment
Нет, это неправильно, он должен дать 6   -  person Saeid    schedule 06.09.2016
comment
Как вы думаете, мне стоит рассмотреть случай, когда i == j и Один элемент считается подмассивом эээ .. Хороший улов @ sudomakeinstall2!   -  person Khalil Khalaf    schedule 06.09.2016
comment
Нет, его логика неверна. Пишу полный ответ прямо сейчас.   -  person Saeid    schedule 06.09.2016
comment
@ sudomakeinstall2 Я сдаюсь :(   -  person Khalil Khalaf    schedule 06.09.2016
comment
Это C ++, поэтому subarray_state_type может быть полезен для ввода и вывода. Возможно с началом, концом, значением. Вы можете использовать именованную константу для NOT_CALCULATED, возможно, stackoverflow.com / questions / 3803961 / c-maximum-non-negative-int. Также может быть полезен std :: vector.   -  person Kenny Ostrom    schedule 06.09.2016

Ответы (1)


arrow_upward
4
arrow_downward

У вашего алгоритма есть логические проблемы, и он не оптимален. Вы даже не используете значения 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 = макс (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 = сумма (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) время.

person Saeid    schedule 06.09.2016
comment
Это определенно заслуживает большего количества голосов. Он подчеркивает логическую ошибку в моем коде (который, как мне казалось, был идеальным), он обеспечивает дизайн для правильного подхода, он обеспечивает дизайн для решения моей проблемы, а не только исходную проблему (моя проблема состоит в том, чтобы также предоставить индексы) и, кроме того, он обеспечивает новую реализацию с меньшими затратами времени! Снимаю шляпу за тяжелую работу :) Я все равно попытаюсь исправить свой код, но это идеальный ответ. Я редактирую заголовок для использования этого Q, чтобы отмечать другие Q в будущем как дубликаты этого. - person Khalil Khalaf; 06.09.2016