c++ - 至少长度为 L 的最大连续子序列和(递归)

Question

int maxSumRec( const vector<int> & a, int left, int right )
{
    if( left == right )  // Base case
        return a[ left ];

    int center = ( left + right ) / 2;
    int maxLeftSum  = maxSumRec( a, left, center );
    int maxRightSum = maxSumRec( a, center + 1, right );

    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for( int i = center; i >= left; i-- )
    {
        leftBorderSum += a[ i ];
        if( leftBorderSum > maxLeftBorderSum )
            maxLeftBorderSum = leftBorderSum;
    }

    int maxRightBorderSum = 0, rightBorderSum = 0;
    for( int j = center + 1; j <= right; j++ )
    {
        rightBorderSum += a[ j ];
        if( rightBorderSum > maxRightBorderSum )
            maxRightBorderSum = rightBorderSum;
    }

    return max3( maxLeftSum, maxRightSum,
                maxLeftBorderSum + maxRightBorderSum );
}

此函数将返回 vector 的最大连续子序列。任务是实现一个称为“L”的最小序列参数，然后返回至少长度为 L 的最大连续子序列。

例子:没有L参数:

vector<int> a(4);
a[ 0 ] = 1; a[ 1 ] = 3; a[ 2 ] = -20; a[ 3 ] = 7;
maxSumRec(a, 0, a.size() - 1);

将返回“7”

示例:带 L 参数:

int L = 3;
vector<int> a(4);
a[ 0 ] = 1; a[ 1 ] = 3; a[ 2 ] = -20; a[ 3 ] = 7;
maxSumRec(a, 0, a.size() - 1, L);

会返回“-9”

我知道这可以通过其他不同的最大总和函数轻松完成，但该任务明确适用于此递归公式。我什至不知道如何开始。教授给了我们这样的工作提示:“将 minSeq 添加到递归算法中的主要困难在于边界和计算。 显然，我们可以假设两个边界序列中的每一个都必须包含至少一个元素，否则 对面的递归调用已经找到了最优解。在另一 另一方面，在不知道 minSeq-k 会发生什么的情况下，我们不知道一侧的 k 个元素是否足够 另一边的元素。似乎需要进行一些搜索，并且会增加最坏的情况 算法的运行时间受与 minSeq 相关的某些因素影响。”

Answer 1

int maxSumRec( const vector<int> & a, int left, int right, int L )
{
	int center = ( left + right ) / 2;
	...
	int maxBorderSum = 0, leftBorderSum = 0;
    // for( int i = center; i >= left; i-- )
    // {
        // ...
    // }

    // int maxRightBorderSum = 0, rightBorderSum = 0;
    // for( int j = center + 1; j <= right; j++ )
    // {
        // ...
    // }	
	int partialSum[1000] = {0}, dpR[1000] = {0};
	for(int i = center + 1; i <= right; i++) 
		partialSum[i] += partialSum[i-1];
	for(int i = right; i > center; i--)  
		dpR[i-center] = max(partialSum[i], dpR[i-center+1]);
	
	for(int i = center; i >= left; i--){
		leftBorderSum += a[i];
		int leftLength = center - i + 1;
		int minRightLength = L - leftLength;
		maxBorderSum = max(maxLeftBorderSum, leftBorderSum + dpR[minRightLength]);
	}
		
	...
	return max3( maxLeftSum, maxRightSum, maxBorderSum);
}

我的想法是将注释部分替换成这样的东西(有点伪，只是为了演示这个想法)

首先，我计算 partialSum[] 和 dpR[] ，两者都使用 O(n)

partialSum[i] = 从 a[center] 到 a[i] 的总和

dpR[i] = 至少长度为 i 的中心右侧的最大和

现在我们得到了特定长度右侧区域的最大总和，我们可以找到至少长度为 L 的边界总和:

对于你选择的每一个左边的元素，假设你选择了3个元素，我们找到dpR[L-3]并将它们相加得到总和，我们在这个过程中取最大值

(注意:代码是为了说明目的，你应该知道那些小东西，比如你必须至少每边选择一个元素；计算 partialSum[] 和 dpR[]等)