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

Question

我有一个线性时间最大连续子序列求和算法，它假定最小子序列长度仅为 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) 的任何提示？我完全被难住了。

Answer 1

创建一个 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;
}