寻找最大子数组的分而治之算法 - 如何同时提供结果子数组索引？

Question

打扰一下，我有一个任务要解决Maximum Sub Array Problem using the Brute Force Algorithm O(n^2), Divide and Conquer O(nlogn) and 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;
}

Answer 1

你的算法逻辑有问题，不是最优的。您甚至没有使用 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 = 总和（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;
}

注意： 该算法运行 O(n) 时间。

Answer 2

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MINUS_INFINITY -1e10

float Find_max_cross_subarray(int I[],float A[]){

    float left_sum = MINUS_INFINITY;
    float right_sum = MINUS_INFINITY;
    float sum = 0;
    int left_max,right_max,i;

    for(i=I[2];i>=I[0];i--){
        sum = sum + A[i];
        if(sum > left_sum){
        left_sum = sum;
        left_max = i;
        }
    }
     sum = 0;
    for(i=I[2]+1;i<=I[1];i++){
    sum = sum + A[i];
    if(sum > right_sum){
        right_sum = sum;
        right_max = i;
    }
}
I[0] = left_max;
I[1] = right_max;
sum = left_sum + right_sum;
return sum;
}

float Find_max_subarray(int I[],float A[]){

int sum,mid;
int left[2];
int right[2];
int cross[3];
float left_sum,right_sum,cross_sum;
if(I[0] == I[1]){
    sum = A[I[0]];
}
else {
    mid = floor((I[0]+I[1])/2);
    left[0] = I[0];
    left[1] = mid;
    right[0] = mid + 1;
    right[1] = I[1];
    cross[0] = I[0];
    cross[1] = I[1];
    cross[2] = mid;
    left_sum = Find_max_subarray(left,A);
    right_sum = Find_max_subarray(right,A);
    cross_sum = Find_max_cross_subarray(cross,A);
    if((left_sum >= right_sum)&&(left_sum >= cross_sum)){
        sum = left_sum;
        I[0] = left[0];
        I[1] = left[1];
    }
    else if((right_sum >= left_sum)&&(right_sum >= cross_sum)){
        sum = right_sum;
        I[0] = right[0];
        I[1] = right[1];
    }
    else{
        sum = cross_sum;
        I[0] = cross[0];
        I[1] = cross[1];
    }
}
return sum;
}

int main(){

int n,i;
float max_sum;
int I[2];

float A[100] = {13, -3, -25, 20, -3,-16,-23,18,20,-7,12,-5,-22,15,-4,7}; 
n = sizeof(A)/sizeof(A[0]); 
I[0] = 0;
I[1] = n-1;
max_sum = Find_max_subarray(I,A);
printf("Maximum sub array is A[%d ......%d] with sum %f",I[0],I[1],max_sum);

}

寻找最大子数组的分而治之算法 - 如何同时提供结果子数组索引？

Divide and Conquer Algorithm for Finding the Maximum Subarray - How to also provide the result subarray indexes?

c++

algorithm

recursion

logic

divide-and-conquer