具有开始和结束索引的最大子数组

Question

我试图找到具有开始和结束索引的最大连续子数组。我采用的方法是分而治之，时间复杂度为O(nlogn)。

我用几个测试用例进行了测试，开始和结束索引始终正常工作。但是，我发现如果数组包含奇数个元素，最大和有时是正确的，有时是错误的（看似随机）。但对于偶数情况，它总是正确的。这是我的代码：

int maxSubSeq(int A[], int n, int &s, int &e)
{   
    // s and e stands for start and end index respectively, 
    // and both are passed by reference

    if(n == 1){
        return A[0];
    }

    int sum = 0;
    int midIndex = n / 2;
    int maxLeftIndex = midIndex - 1;
    int maxRightIndex = midIndex;

    int leftMaxSubSeq = A[maxLeftIndex]; 
    int rightMaxSubSeq = A[maxRightIndex];

    int left = maxSubSeq(A, midIndex, s, e);
    int right = maxSubSeq(A + midIndex, n - midIndex, s, e);

    for(int i = midIndex - 1; i >= 0; i--){
        sum += A[i];
        if(sum > leftMaxSubSeq){
            leftMaxSubSeq = sum;
            s = i;
        }
    }
    sum = 0;
    for(int i = midIndex; i < n; i++){
        sum += A[i];
        if(sum > rightMaxSubSeq){
            rightMaxSubSeq = sum;
            e = i;
        }
    }

    return max(max(leftMaxSubSeq + rightMaxSubSeq, left),right);   
}

下面是我使用的两个测试用例，一个有奇数元素，一个有偶数元素。

Array with 11 elements:
  1,   3,  -7,   9,   6,   3,  -2,   4,  -1,  -9, 
  2,
Array with 20 elements:
  1,   3,   2,  -2,   4,   5,  -9,  -4,  -8,   6, 
  5,   9,   7,  -1,   5,  -2,   6,   4,  -3,  -1,

编辑：以下是2种输出：

// TEST 1
Test file : T2-Data-1.txt
Array with 11 elements:
  1,   3,  -7,   9,   6,   3,  -2,   4,  -1,  -9, 
  2, 

maxSubSeq : A[3..7] = 32769 // Index is correct, but sum should be 20

Test file : T2-Data-2.txt
Array with 20 elements:
  1,   3,   2,  -2,   4,   5,  -9,  -4,  -8,   6, 
  5,   9,   7,  -1,   5,  -2,   6,   4,  -3,  -1, 

maxSubSeq : A[9..17] = 39 // correct

// TEST 2

Test file : T2-Data-1.txt
Array with 11 elements:
  1,   3,  -7,   9,   6,   3,  -2,   4,  -1,  -9, 
  2, 

maxSubSeq : A[3..7] = 20

Test file : T2-Data-2.txt
Array with 20 elements:
  1,   3,   2,  -2,   4,   5,  -9,  -4,  -8,   6, 
  5,   9,   7,  -1,   5,  -2,   6,   4,  -3,  -1, 


maxSubSeq : A[9..17] = 39

谁能指出为什么会这样？提前致谢！

Answer 1

假设 n 是您数组的正确大小（我们看到它作为参数传入，稍后用于初始化 midIndex 但是我们没有看到它的实际调用，所以必须假设你做的是正确的），问题出在这里：

int midIndex = n / 2;

如果你的数组有奇数个元素，我们可以表示为

n = 2k + 1

我们可以发现你的中间索引总是等于

(2k + 1) / 2 = k + (1/2)

这意味着对于每个整数 k，您总会将整数的一半添加到 k。

C++ 不会舍入接收浮点数的整数；它截断。所以当你期望 k + 0.5 舍入到 k+1 时，你实际上得到 k截断后。

这意味着，例如，当您的数组大小为 11 时，midIndex 被定义为 5。因此，您需要相应地调整您的代码。

具有开始和结束索引的最大子数组

Max subarray with start and end index

c++

algorithm

divide-and-conquer