c++ - 指定最小长度的线性时间最大连续子序列求和算法

我有一个线性时间最大连续子序列求和算法，它假设最小子序列长度仅为 0:

int maxSubSum4(const vector<int> & a, const int &minSeq)
{
    int maxSum = 0, thisSum = 0;

    for (int j = 0; j < a.size(); j++)
    {
        thisSum += a[j];

        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
    }

    return maxSum;
}

关于如何更新它以处理正用户指定的最小子序列长度( minSeq )的任何提示？我完全被难住了。

最佳答案

创建一个 minSeq 长度总和数组，这将是您的下限:

int maxSubSum5(const vector<int> & a, const int &minSeq){
  if(minSeq > a.size()) throw logic_error("maxSubSum5 - minSeq too big!");
  if(minSeq == 0) return maxSubSum4(a, minSeq);

  vector<int> minimal(a.size()-minSeq+1);
  minimal[0] = 0;
  for(size_t i=0; i<minSeq; ++i) minimal[0] += a[i];
  for(size_t i=1; i<minimal.size(); ++i) {
    minimal[i] = minimal[i-1] - a[i-1] + a[i+minSeq-1];
  }

  int maxSum = minimal[0], currentSum = maxSum;
  for(size_t i=minSeq; i<a.size(); ++i){
    currentSum += a[i];
    if(currentSum < minimal[i-minSeq+1]) currentSum = minimal[i-minSeq+1];
    if(currentSum > maxSum) maxSum = currentSum;
  }
  return maxSum;
}

(每当我们重置 currentSum 时，我们都会切断子序列 s ，其中包含最后一个元素的 s 的任何子序列都具有负和。)

更新: 由于我们只使用 minimal 的每个值一次，它们可以“即时”计算，而无需使用 O(N) 空间。这也使代码更短:

int maxSubSum5(const vector<int> & a, const int &minSeq){
  if(minSeq > a.size()) throw logic_error("maxSubSum5 - minSeq too big!");
  if(minSeq == 0) return maxSubSum4(a, minSeq);

  int minimalSum = 0;
  for(size_t i=0; i<minSeq; ++i) minimalSum += a[i];

  int maxSum = minimalSum, currentSum = minimalSum;
  for(size_t i=minSeq; i<a.size(); ++i){
    currentSum += a[i];
    minimalSum += a[i] - a[i-minSeq];
    if(currentSum < minimalSum) currentSum = minimalSum;
    if(currentSum > maxSum) maxSum = currentSum;
  }
  return maxSum;
}

关于c++ - 指定最小长度的线性时间最大连续子序列求和算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33293532/