Linear-time maximum contiguous subsequence sum algorithm with a specified minimum length

Question

I have a linear-time maximum contiguous subsequence sum algorithm which assumes that the minimum subsequence length is just 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;
}

Any hints for how this could be updated to handle positive user specified minimum subsequence lengths (minSeq)? I am completely stumped.

Answer 1

Create an array of minSeq length sums, that will be your lower bound:

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

(Whenever we reset currentSum, we cut off subsequence s where any subsequence of s which includes last element has negative sum.)

Upd: Since we use each value of minimal only once, they can be calculated "on the fly", without using O(N) space. This makes code shorter, as well:

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