最小长度L（递归）的最大连续子序列和

问题描述：

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

该函数将返回矢量的最大连续子序列。的任务是实现所谓的“L”即然后返回至少长度的最大连续子序列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引起的主要困难是边界和计算显然，我们可以假设两个边界序列中的每一个必须至少包含一个元素，或者否则最佳解决方案已被发现在对面的递归调用。另一方面，我们不知道k元素是否足够在一边而不知道什么发生在minSeq-k 元素上另一方面，似乎需要进行一些搜索，并且会通过与minSeq相关的一些因素增加算法运行时间的最坏情况。“

时最棘手的情况下考虑（比如左）与它ķ

答

int maxSumRec(const vector<int> & a, int left, int right, int L) 
 
{ 
 
\t int center = (left + right)/2; 
 
\t ... 
 
\t 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++) 
 
    // { 
 
     // ... 
 
    // } \t 
 
\t int partialSum[1000] = {0}, dpR[1000] = {0}; 
 
\t for(int i = center + 1; i <= right; i++) 
 
\t \t partialSum[i] += partialSum[i-1]; 
 
\t for(int i = right; i > center; i--) 
 
\t \t dpR[i-center] = max(partialSum[i], dpR[i-center+1]); 
 
\t 
 
\t for(int i = center; i >= left; i--){ 
 
\t \t leftBorderSum += a[i]; 
 
\t \t int leftLength = center - i + 1; 
 
\t \t int minRightLength = L - leftLength; 
 
\t \t maxBorderSum = max(maxLeftBorderSum, leftBorderSum + dpR[minRightLength]); 
 
\t } 
 
\t \t 
 
\t ... 
 
\t return max3(maxLeftSum, maxRightSum, maxBorderSum); 
 
}

我的想法是更换注释部分是这样的（有点假，只是为了验证这个想法）

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

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

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

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

为您挑选的每个左元素，说你挑3个要素，我们发现DPR [1-3]，总结起来得到的总和，我们采取了最大的在这个过程中

（注意：代码是用于说明目的，你应该知道那些小事情，比如你必须至少每边选择一个元素;计算partialSum[]和dpR[]等）

最小长度L（递归）的最大连续子序列和

相关推荐